09 Jul 2006

# Integer Sequence A112088

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```
Results in 3 leafs

# 3rd step: 2, 3, 5

```                .
.   .
.       .
.           .
.               .
. .             . .
.   .           .   .
.     .         .     .
o       o       o       o
.
.
.
o```
Results in 5 leafs

# 4th step: 2, 3, 5, 7

```                            .
.      .
.             .
.                    .
.                           .
.   .                       .   .
.       .                   .       .
.           .               .           .
.              .            .               o
. .            . .          . .
.   .          .   .        .   .
.     .        .     .      .     .
o       o      o       o    o       o```
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.