A079559 prod(n>=1, 1+x^(2^n-1) )

[Joerg Arndt]

[My comments interlaced]

* Lambert Klasen <Lambert.Klasen at gmx.net> [Jul 17. 2005 21:23]:
> Dear seqfans,
> 
> > The funny recursion
> > 
> > void A079559(int f, int n)
> > {
> >     int m;
> >     printf("1,");
> >     for (m=1; m<n; m*=2)  A079559(f+m, m);
> >     printf("0,");
> > }
> > 
> > started with args (0, 2**k) seems to give A079559.
> > Any explanation why that is?
> 
> yes, for some 2^n both seq. do the same.
> it can be seen by stressing another ruler like output of both seqs:
> 
> 110110011011000
> 1101100110110000
> 110110011011000
> 11011001101100000
> 110110011011000
> 1101100110110000
> 110110011011000
> 110110011011000000
> 110110011011000
> 1101100110110000
> 110110011011000
> 11011001101100000
> 110110011011000
> 1101100110110000
> 110110011011000
> 1101100110110000000
> 110110011011000
> 1101100110110000
> 110110011011000
> ....
> 
> it is easy to see that prod(n>=1, 1+x^(2^n-1) ) emerges this way.

Uhm..., I don't see it.


> your program does the same, but
> it is more a nesting than a recursion:
> 
> here the pattern for 
> ./A079559 0 [1 2 3 5 9]
> 
> 1: (1 0)
> 2: (1 (1 0) 0)
> 3: (1 (1 0) (1 (1 0) 0) 0)
> 5: (1 (1 0) (1 (1 0) 0) (1 (1 0) (1 (1 0) 0) 0) 0)
> 9: (1 (1 0) (1 (1 0) 0) (1 (1 0) (1 (1 0) 0) 0) \
>    (1 (1 0) (1 (1 0) 0) (1 (1 0) (1 (1 0) 0) 0) 0) 0)
> 
> 
> best regards
>          Lambert
> 

Looks like what I have found yesterday:
The sequence can also be generated with a string substitution engine

    Start: 1x
    Rules:
      0 --> 0
      1 --> 110
      x --> x
    -------------
    0:   (#=2)
      1x
    1:   (#=4)
      110x
    2:   (#=8)
      1101100x
    3:   (#=16)
      110110011011000x
    4:   (#=32)
      1101100110110001101100110110000x
    5:   (#=64)
      110110011011000110110011011000011011001101100011011001101100000x

Further, the sequence appears as lowest bits in the sequence
of the bit-reversed binary words in reversed lex order.
(binary, dots for zeros):

  ....1
  ...11
  ...1.
  ..1.1
  ..111
  ..11.
  ..1..
  .1..1
  .1.11
  .1.1.
  .11.1
  .1111
  .111.
  .11..
  .1...
  1...1
  1..11
  1..1.
  1.1.1
  1.111
  1.11.
  1.1..
  11..1
  11.11
  11.1.
  111.1
  11111
  1111.
  111..
  11...
  1....

I'll check whether  this sequence is in the OEIS
and add it if not.  Plus I'll add the remarks above.

-- 
p=2^q-1 prime <== q>2, cosh(2^(q-2)*log(2+sqrt(3)))%p=0
Life is hard and then you die.