wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Yet still once again another sequence
        
(Message started by: Icarus on Jan 26^th, 2006, 7:58pm)

Title: Yet still once again another sequence
Post by Icarus on Jan 26^th, 2006, 7:58pm

Can you identify the sequence without using Sloane's Encyclopedia (or similar resources)?

1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765, 4294967295, 4294967297, ...

The sequence is infinite.
Curiously, it is only in the last value I gave that this sequence diverges for the first time from an apparently unrelated sequence in Sloane's Encyclopedia.

hint: [hide]Where do the pairs occur?[/hide]

Title: Re: Yet still once again another sequence
Post by Eigenray on Jan 26^th, 2006, 11:48pm

Iterating the function
F(n) = [sum]_k=0^oo [hide]2^k sin² (pi/2 [(n+2^k-1)/2^k])[/hide],
(where [.] is floor) of course:D. Hence the next term is
F(4294967297) = 12884901891.

Title: Re: Yet still once again another sequence
Post by Icarus on Jan 27^th, 2006, 4:07pm

I'm curious where you got that expression from. That is indeed the next element of the sequence, though my form is far more elementary!

Title: Re: Yet still once again another sequence
Post by Sir Col on Jan 27^th, 2006, 5:10pm

::
[hide]This is quite difficult to put into words, but...

Starting with 1, the sequence is built up in blocks. The key element for the next block is the last term in the previous block plus 2 (or a number of the form 2^{2^k}: 3 = 2^{2^0}+1, 5 = 2^{2^1}+1, 17 = 2^{2^2}+1, 257 = 2^{2^3}+1, 65537 = 2^{2^4}+1, ...). Then the next block is created by multiplying this key element by all the previous elements.

After 1, the key element for the next block is 1+2 = 3. Multiplying 3 by the previous elements gives the new term 3*1 = 3.

So far: 1, 3.

The next key element is 3+2 = 5, and multiplying by the previous elements gives 5*1 = 5 and 5*3 = 15.

So far: 1, 3, 5, 15.

The next key element is 15+2 = 17, and mutliplying by the previous elements gives 17*1 = 17, 17*3 = 51, 17*5 = 85, 17*15 = 255.

So far: 1, 3, 5, 15, 17, 51, 85, 255.

255+2 = 257
257 (1*257), 771 (3*257), ... , 65535 (255*257)

So far: 1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535.

65535+2 = 65537
65537 (1*65537), ... , 4294967295 (65535*65537)

So far: 1, 3, 5, ... , 858993459, 1431655765, 4294967295.

4294967295+2 = 4294967297
4294967297 (1*4294967297), 12884901891 (3*4294967297), and so on.
[/hide]::

Title: Re: Yet still once again another sequence
Post by Eigenray on Jan 27^th, 2006, 5:55pm

on 01/27/06 at 16:07:26, Icarus wrote:

I'm curious where you got that expression from. That is indeed the next element of the sequence, though my form is far more elementary!

From looking at the [hide]pretty picture, and encoding the transformation[/hide]. It was meant to be obfuscated, but I hid it anyway in case [hide]those powers of 2[/hide] gave anything away.

Title: Re: Yet still once again another sequence
Post by Icarus on Feb 11^th, 2006, 9:31am

My derivation: Pascal's triangle in Z₂, treated as the digits of a binary number:

1 = 1
1 1 = 3
1 0 1 = 5
1 1 1 1 = 15
1 0 0 0 1 = 17
1 1 0 0 1 1 = 51
1 0 1 0 1 0 1 = 85
...

Now: why I posted it... Go look this sequence up in Sloane's On-Line Encyclopedia of Integer Sequences (http://www.research.att.com/~njas/sequences/), using at most one fewer elements than I listed in the first post, and you will find a second sequence, distinct from this one: a_n is the smallest number whose Euler totient is divisible by 2ⁿ.

These two apparently unrelated sequences march in lock-step for 32 values before finally parting company and going their separate ways. Indeed, while our Pascal-based sequence necessarily is always odd, the Euler-based sequence at this point switches over to even values, and stays even as far as is currently known.

Can anyone explain this seeming coincidence?
A hint may be found [hide]in the third, finite, sequence that also turns up in Sloane.[/hide]

Title: Re: Yet still once again another sequence
Post by Eigenray on Feb 11^th, 2006, 7:58pm

The elements of the Pascal-based sequence are precisely the products of distinct Fermat numbers F_n=2^{2^n}+1. Specifically, if n = a₀+a₁2+...+a_k2^k in binary, then the n-th term is
P_n = F₀^a_0 . . . F_k^a_k.
In fact, Sir Col takes this as the definition: if 0< n < 2^k, then
P_2^k+n = F_k*P_n.
One way to derive this from the Pascal's triangle definition is to consider the polynomial
(1+x)ⁿ = [prod] (1+x)^{a_i 2^i}
[sum] (ⁿC_r) x^r == [prod] (1+x^{2^i})^a_i,
where the last == is equality as polynomials over Z₂, i.e., for each power of x, the coefficients on both sides have the same parity. But note that if we expand out the RHS, each coefficient will be either 0 or 1: there are no "like terms" to combine. Thus letting {ⁿ_r} be the reduction of (ⁿC_r) mod 2, we have equality as polynomials over Z:
[sum] {ⁿ_r} x^r = [prod] (1+x^{2^i})^a_i.
Setting x=2 gives the result.

On the other hand, each term of the Euler-based sequence is either a power of 2, or a product of distinct Fermat primes. To see this, suppose m is the smallest number with 2ⁿ|phi(m). Since we have phi(2ⁿ⁺¹)=2ⁿ, this means
2ⁿ | phi(m) < m < 2ⁿ⁺¹,
and it follows phi(m)=2ⁿ. Now, if a prime p|m, then (p-1)|phi(m), so p-1 must be a power of two. This requires either p=2 or p=F_i, a Fermat prime. And we can't have F_i²|m, for otherwise F_i|phi(m), impossible. So m has the form
m = 2^k F_{i_1}...F_{i_r},
with the F_{i_j} distinct Fermat primes (k,r>0). Suppose that k>0 and r>0. Then
phi(m) = 2^k-1 2^{2^i1} ... 2^{2^ir} = phi(2^{k+2^i1+...+2^ir}).
But 2^k2^{2^i1}...2^{2^ir} < m, contradicting our choice of m. Thus either k=0, and m is a product of distinct Fermat primes, or r=0, and m is a power of 2.

Finally, suppose m is a product of distinct Fermat primes, say phi(m) = 2ⁿ. Then n has a unique binary expansion, so m is the only odd number with totient 2ⁿ. And since
phi(m)/m > [prod]_i=0^oo (1 - 1/F_i) = 1/2,
we have m < 2ⁿ⁺¹, and it follows that m does appear in the sequence.

Thus the Euler-based sequence consists of all products of distinct Fermat primes, but with powers of 2 added to fill in the "gaps". As an example, if there ends up being another Fermat prime F_N, then the sequence will contain
..., 2^{2^N-1}, 2^{2^N}, F_N, F₀F_N, F₁F_N, F₀F₁F_N, ..., F₀F₁F₂F₃F₄F_N, 2^{2^N+33}, 2^{2^N+34}, ...

Now, since F₀,...,F₄ are all prime, we can see why the divisors of F₀F₁...F₄=2³²-1 make up the first 32 terms from both sequences.