## next number in this infinite sequence?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

### next number in this infinite sequence?

so I was reading GEB and I thought of a cool sequence
1 3 8 20 48 112 256

OEIS doesn't have it so I was wondering if any of you can find the pattern
Last edited by 4=5 on Wed Jun 11, 2008 4:50 pm UTC, edited 1 time in total.

4=5

Posts: 2068
Joined: Sat Apr 28, 2007 3:02 am UTC

### Re: next number in this infinite sequence?

Should the sixth and seventh terms be 112 and 256? If so, then I know how the sequence was generated, though I haven't yet got an explicit formula.
limu->i(patience)=0
Robin S

Posts: 3557
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK

### Re: next number in this infinite sequence?

yes, thank you.
hmm it turns out OEIS does have it

4=5

Posts: 2068
Joined: Sat Apr 28, 2007 3:02 am UTC

### Re: next number in this infinite sequence?

Here's one possible way of obtaining the sequence:

Spoiler:
Given the nth term, double it and add 2n-1 to get the n+1th term.

The sequence does appear in OEIS, here.
limu->i(patience)=0
Robin S

Posts: 3557
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK

### Re: next number in this infinite sequence?

Spoiler:
So in general, letting s0 = 1 and s1 = 3, we get that sn = (n+2)2n-1.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Cauchy

Posts: 374
Joined: Wed Mar 28, 2007 1:43 pm UTC

### Re: next number in this infinite sequence?

I'm no expert at maths (I don't even know what OEIS is lol ) but I found the sequence pretty easy to work out ....

Spoiler:
Starting with the first number = 1 .... double it and add 1 to get the 2nd number = 3.
Double this and add 2 to give 8.
Double this and add 4 to give 20.
Double this and add 8 to give 48.
Double this and add 16 to give 112.
Double this and add 32 to give 256.
Double this and add 64 to give (*taps away on calculator*) 576.

Moonbeam

Posts: 223
Joined: Sat Dec 08, 2007 5:28 pm UTC
Location: UK

### Re: next number in this infinite sequence?

The partial sums of this finite sequence are:
1 4 12 32 80 192 448
so the nth partial sum seems to be:
n*2n-1

This means the nth partial sum represents
Spoiler:
the number of "1s" used when writing out the first 2n nonnegative integers in binary, since each of the n binary place values will be "1" exactly half of the time on this range.

Since that is what the partial sums represent, then the nth term anin the original sequence must represent the number of "1s" used when writing out only the integers from 2n-1 to 2n-1 (i.e. the "n bit long" integers).

Thus we would expect the sequence to satisfy the recurrence (found by Robin S and Moonbeam):
a1=1
an+1=2*an+2n-1
for n>0, since the collection of all n+1 bit long integers is just the collection of all n bit long integers that have a "0" or "1" tacked on to the end.

I'm curious about the connection to GEB; does this sequence have something to do with Hofstadter's "G diagram" or "H diagram"? That's the only thing I could think of.
Hix

Posts: 364
Joined: Sun Oct 15, 2006 5:46 pm UTC

### Re: next number in this infinite sequence?

it has very little to do with GEB, I just thought of it while reading it and trying to figure out what this meant
Spoiler:
the reason I found it interesting was because when you find the difference and then the difference of the difference and then the difference of the difference of he difference it counts up "1,2,3,4,5,6,7" if you use the first digit of each layer after.

4=5

Posts: 2068
Joined: Sat Apr 28, 2007 3:02 am UTC

### Re: next number in this infinite sequence?

4=5 wrote:it has very little to do with GEB, I just thought of it while reading it and trying to figure out what this meant
Spoiler:
the reason I found it interesting was because when you find the difference and then the difference of the difference and then the difference of the difference of he difference it counts up "1,2,3,4,5,6,7" if you use the first digit of each layer after.

What you're talking about is the first, second, and third differences.

And yes, it does do that. So the equation is polynomial, and quartic.
tricky77puzzle
Will take "No Tresspassing Signs" for 500

Posts: 488
Joined: Thu Feb 28, 2008 11:02 pm UTC

### Re: next number in this infinite sequence?

What? No, it isn't quartic - Cauchy gives the formula above.
limu->i(patience)=0
Robin S

Posts: 3557
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK

### Re: next number in this infinite sequence?

Eh, bellow isn't a hint but it does give a method of finding the next term in the sequence... not nearly as useful as the formula though.
Spoiler:
I know this is probably given by the formula's... well definently since they both refer to the same sequence, but first thing I noticed was that to get the next term in the sequence, you take your current term, multiply it by three, and subtract the sum of the previous terms...
kilik

Posts: 17
Joined: Mon Mar 31, 2008 10:15 pm UTC

### Re: next number in this infinite sequence?

look at the the difference between each term in the sequence:

Spoiler:
2*1+0=2
2*2+1=5
2*5+2=12
2*12+4=28
2*28+8=64
2*64+16=144
2*144+32= 320

etc etc..... see the pattern? so we have:
1 (+2) 3 (+5) 8 (+12) 20(+28) 48 (+64) 112 (+144) 256 (+320) 576........

to me that was the most obvious pattern I'm sure there are dozens more

Tez

Posts: 52
Joined: Wed Jul 02, 2008 11:59 pm UTC
Location: Sydney

### Re: next number in this infinite sequence?

{1, 3, 8, 20, 48, 112, 256, 576, 1280, 2816, 6144, 13312, 28672, 61440, 131072, 278528, 589824, 1245184, 2621440, 5505024, 11534336, 24117248, 50331648, 104857600, 218103808, 452984832, 939524096, 1946157056}

a(n)= (n+1)*2^(n-2)
ARP

Posts: 4
Joined: Thu Apr 26, 2012 6:49 pm UTC

### Re: next number in this infinite sequence?

ARP wrote:a(n)= (n+1)*2^(n-2)

I worked out (and I've not done pure maths in a long time so am feeling rather proud of myself) that a(n) = [(n+1)/2]*2^(n-1), which I proved to be equal to yours (n+1)*2^(n-2), and can be proven to give the same sequence as the OEIC's result (n+2)*2^(n-1). For our two sequences, start at n=1, for OEIC's start at n=0.

I think that's right. This is the first bit of pure maths I've done in ages and it's good to get some practice in. Feel free to point out any errors.

Posts: 6
Joined: Wed Jul 11, 2012 2:00 am UTC
Location: Manchester, UK

### Re: next number in this infinite sequence?

When checking for polynomial, solutions, I found this fun pattern.

Spoiler:
1 3 8 20 48 112 256 576

2 5 12 28 64 144 320

3 7 16 36 80 176

4 9 20 44 96

5 11 24 52

6 13 28

7 15

8

I also see
Spoiler:
f(n) = f(n-1)*2 + 2^(n-1), which also gets 576

sam_i_am

Posts: 563
Joined: Mon Jun 18, 2012 3:38 pm UTC
Location: Urbana, Illinois, USA

### Re: next number in this infinite sequence?

4=5 wrote:so I was reading GEB and I thought of a cool sequence
1 3 8 20 48 112 256

OEIS doesn't have it so I was wondering if any of you can find the pattern

The next number is 4.

The number after that is 4.

In fact, the whole sequence after the first seven terms is all 4’s.
Small Government Liberal

Qaanol

Posts: 2395
Joined: Sat May 09, 2009 11:55 pm UTC