09 Jul 2006

Integer Sequence A112088

By Simon Strandgaard.

Idea: Add the same number of edges as there are leafs in the previous step.

This sequence has been entered as A112088 in the On-Line Encyclopedia of Integer Sequences.

2, 3, 5, 7, 11, 16, 24, 36, 54, 81, 122, 183, 274, 411, 617, 925, 1388, 2082, 3123, 4684, 7026, 10539, 15809, 23713, 35570, 53355, 80032, 120048, 180072, 270108, 405162, 607743, 911615, 1367422, 2051133, 3076700, 4615050, 6922575, 10383862

1st step: 2

    .
   . .
  .   .
 .     .
o       o
Starting out with 2 leafs

2nd step: 2, 3

        .
       . .
      .   .
     .     .
    .       o
   . .
  .   .
 .     .
o       o
Adding 2 edges
Results in 3 leafs

3rd step: 2, 3, 5

                .
              .   .
            .       .
          .           .
        .               .
       . .             . .
      .   .           .   .
     .     .         .     .
    o       o       o       o
   .
  .
 .
o
Adding 3 edges
Results in 5 leafs

4th step: 2, 3, 5, 7

                            .
                        .      .
                    .             .
                .                    .
            .                           .
          .   .                       .   .
        .       .                   .       .
      .           .               .           .
    .              .            .               o
   . .            . .          . .
  .   .          .   .        .   .
 .     .        .     .      .     .
o       o      o       o    o       o
Adding 5 edges
Results in 7 leafs

5th step: 2, 3, 5, 7, 11

                                             .
                                      .             .          
                                .                         .
                          .                                     .
                      .                                             .
                   .     .                                       .     .
                .           .                                 .           .
             .                 .                           .                 .
          .                       .                     .                       .
        .   .                   .   .                 .   .                   .   .
      .       .               .       .             .       .               .       .
     .         .             .         .           .         .             .         .
    .           .           o           o         o           o           o           o
   . .         . .         .                                 
  .   .       .   .       .                               
 .     .     .     .     .                           
o       o   o       o   o
Adding 7 edges, Results in 11 leafs

6th step: 2, 3, 5, 7, 11, 16

                                              .
                                      .               .          
                                .                           .
                          .                                       .
                      .                                               .
                   .     .                                         .     .
                .           .                                   .           .
             .                 .                             .                 .
          .                       .                       .                       .
        .   .                   .   .                   .   .                   .   .
      .       .               .       .               .       .               .       .
     .         .             .         .             .         .             .         .
    .           .           .           .           .           .           .           .
   . .         . .         . .         . .         . .         . .         . .         . .
  .   .       .   .       .   .       .   .       .   .       .   .       .   .       .   .
 .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .
o       o   o       o   o       o   o       o   o       o   o       o   o       o   o       o
Adding 11 edges, Results in 16 leafs

N'th step: 2, 3, 5, 7, 11, 16, ...

Originally I (Simon Strandgaard) submitted this Ruby oneliner:

a, c=2, 4; p Array.new(99){c-=x=(a*4-c+1)/2; c+=2*a*=2 if c<0; x}
#=> [2, 3, 5, 7, 11, 16, 24, 36, 54, 81, 122, 183, ...]

And recently Graeme McRae has made this formula for it:

a(1)=2; a(n)=floor((5+sum(a(1) to a(n-1)))/2)

Also recently, I found that it was referenced in MathForum, discussing the Josephus problem. I have never heard about Josephus, and I have no idea if there exists a connection.

Story about A112088

I have always been facinated by things that mimics the prime numbers. While playing with these things I made up this sequence. My friend Johan Gade told me about The On-Line Encyclopedia of Integer Sequences, where this sequence was entered. It felt really good :-)