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.

# 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 :-)