This product of Fermat numbers in the discussion below made me think more about Fermat *relative* primes. According to Goldbach's *theorem* (not the conjecture), the Fermat numbers are all *relatively prime* to one another. https://en.wikipedia.org/wiki/Fermat_number Sooooo, the Chinese remainder theorem (CRT) can be used to represent integers mod each and all of the Fermat numbers. CRT arithmetic can be done in parallel, and in this instance it will be dominated by the computation mod the largest Fermat number -- in this case the one whose bits are half the word size. I seem to recall Knuth spending some time talking about clever ways to do arithmetic mod 2^n-1, but I don't recall if he discussed clever ways to do arithmetic mod 2^n+1. Somehow, you'd need a vector of extra bits, one per word. We've done this for ages with "tag bits" in various implementations of Lisp; perhaps similar techniques would work for 2^n+1 arithmetic. At 10:39 PM 7/6/2016, Bill Gosper wrote:

On 2016-07-06 07:13, Henry Baker wrote:

...

Is it just me, or does anyone else find this property pretty cool:

(%i1) x^256-1,factor; 2 4 8 16 32 64 128 (%o1) (x - 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1) (x + 1)

I.e., the factors of 2^2^n-1 are (2^n-1) and (2^2^k+1) for k<n.

This property has to be useful for some recursions on computer word sizes, but I don't recall Knuth using it anywhere.

Is anyone aware of *any* interesting use of this property?

It has to be prominent in Knuth (+Graham+Patashnik):

it's the generating function of 1,1,1,1, ... and illustrates the uniqueness of binary notation:

In[1727]:= Product[1 + x^2^n, {n, 0, ∞}]

Out[1727]= 1/(1 - x)

Closely related:

In[1728]:= Product[Cos[t/2^n], {n, ∞}]

Out[1728]= Sinc[t]

--rwg

The analysis of Karatsuba's multiplication speedup recurses on bisected word length.

Or precision, anyway.

https://en.wikipedia.org/wiki/Anatoly_Karatsuba

pictures him as not the least Japanese, so the stress is on the TSU:

Карацу́ба