Author |
Topic: Yet still once again another sequence (Read 843 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Yet still once again another sequence
« on: Jan 26th, 2006, 7:58pm » |
 Quote  Modify
|
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: Where do the pairs occur?
|
| « Last Edit: Jan 26th, 2006, 8:00pm by Icarus » |
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Yet still once again another sequence
« Reply #1 on: Jan 26th, 2006, 11:48pm » |
Quote Modify
|
Iterating the function
F(n) = [sum]k=0oo 2k sin2 (pi/2 [(n+2k-1)/2k]),
(where [.] is floor) of course . Hence the next term is
F(4294967297) = 12884901891.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Yet still once again another sequence
« Reply #2 on: Jan 27th, 2006, 4:07pm » |
Quote Modify
|
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!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Yet still once again another sequence
« Reply #3 on: Jan 27th, 2006, 5:10pm » |
Quote Modify
|
::
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 22^k: 3 = 22^0+1, 5 = 22^1+1, 17 = 22^2+1, 257 = 22^3+1, 65537 = 22^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.
::
|
| « Last Edit: Jan 28th, 2006, 1:35am by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Yet still once again another sequence
« Reply #4 on: Jan 27th, 2006, 5:55pm » |
Quote Modify
|
on Jan 27th, 2006, 4:07pm, 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 pretty picture, and encoding the transformation. It was meant to be obfuscated, but I hid it anyway in case those powers of 2 gave anything away.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Yet still once again another sequence
« Reply #5 on: Feb 11th, 2006, 9:31am » |
Quote Modify
|
My derivation: Pascal's triangle in Z2, 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, using at most one fewer elements than I listed in the first post, and you will find a second sequence, distinct from this one: an is the smallest number whose Euler totient is divisible by 2n.
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 in the third, finite, sequence that also turns up in Sloane.
|
| « Last Edit: Feb 24th, 2007, 6:59pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Yet still once again another sequence
« Reply #6 on: Feb 11th, 2006, 7:58pm » |
Quote Modify
|
The elements of the Pascal-based sequence are precisely the products of distinct Fermat numbers Fn=22^n+1. Specifically, if n = a0+a12+...+ak2k in binary, then the n-th term is
Pn = F0a_0 . . . Fka_k.
In fact, Sir Col takes this as the definition: if 0< n < 2k, then
P2^k+n = Fk*Pn.
One way to derive this from the Pascal's triangle definition is to consider the polynomial
(1+x)n = [prod] (1+x)a_i 2^i
[sum] (nCr) xr == [prod] (1+x2^i)a_i,
where the last == is equality as polynomials over Z2, 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 {nr} be the reduction of (nCr) mod 2, we have equality as polynomials over Z:
[sum] {nr} xr = [prod] (1+x2^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 2n|phi(m). Since we have phi(2n+1)=2n, this means
2n | phi(m) < m < 2n+1,
and it follows phi(m)=2n. 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=Fi, a Fermat prime. And we can't have Fi2|m, for otherwise Fi|phi(m), impossible. So m has the form
m = 2k Fi_1...Fi_r,
with the Fi_j distinct Fermat primes (k,r>0). Suppose that k>0 and r>0. Then
phi(m) = 2k-1 22^i1 ... 22^ir = phi(2k+2^i1+...+2^ir).
But 2k22^i1...22^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) = 2n. Then n has a unique binary expansion, so m is the only odd number with totient 2n. And since
phi(m)/m > [prod]i=0oo (1 - 1/Fi) = 1/2,
we have m < 2n+1, 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 FN, then the sequence will contain
..., 22^N-1, 22^N, FN, F0FN, F1FN, F0F1FN, ..., F0F1F2F3F4FN, 22^N+33, 22^N+34, ...
Now, since F0,...,F4 are all prime, we can see why the divisors of F0F1...F4=232-1 make up the first 32 terms from both sequences.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print