An integer sequence puzzle

CraigD · 06-27-2009

Consider the integer sequence beginning with these 512 integers: 1,2,2,2,3,3,3,2,3,4,5,3,4,4,4,2,3,4,5,4,6,6,3,3,5, 5,6,4,5,5,5,2,3,4,5,4,6,6,7,4,5,7,7,6,8,4,4,3,5,6, 5,5,8,7,7,4,6,6,7,5,6,6,6,2,3,4,5,4,6,6,7,4,6,7,9, 6,7,8,5,4,6,6,8,7,7,8,7,6,9,9,5,4,6,5,5,3,5,6,6,6, 9,6,7,5,6,9,8,7,8,8,4,4,7,7,8,6,9,8,8,5,7,7,8,6,7, 7,7,2,3,4,5,4,6,6,7,4,6,7,9,6,8,8,9,4,5,7,7,7,9,10 ,6,6,9,8,10,8,5,6,6,4,6,7,9,6,8,9,9,7,9,8,8,8,9,8, 9,6,8,10,9,9,13,6,6,4,7,7,6,5,7,6,6,3,5,6,6,6,9,7, 8,6,9,10,8,6,6,8,8,5,7,7,10,9,8,9,7,7,11,9,10,8,10 ,5,5,4,7,8,7,7,9,9,7,6,6,10,11,8,10,9,9,5,8,8,9,7, 10,9,9,6,8,8,9,7,8,8,8,2,3,4,5,4,6,6,7,4,6,7,9,6,8 ,8,9,4,6,7,9,7,10,10,5,6,8,9,9,8,9,10,6,4,6,6,8,7, 10,8,10,7,7,10,10,10,9,7,8,6,9,10,7,8,11,11,10,8,1 1,6,8,6,6,7,7,4,6,7,9,7,9,10,8,6,9,9,12,9,8,10,9,7 ,10,10,8,8,9,9,9,8,9,10,10,8,11,10,7,6,9,9,9,10,11 ,10,12,9,10,14,7,6,6,7,6,4,8,8,8,7,11,7,7,5,8,8,7, 6,8,7,7,3,5,6,6,6,9,7,8,6,9,10,9,7,10,9,10,6,7,10, 10,10,7,9,7,6,9,7,10,8,8,9,6,5,8,8,10,7,9,11,11,9, 7,9,8,9,11,8,9,7,9,12,9,9,12,11,9,8,12,11,12,5,7,6 ,6,4,7,8,8,8,8,8,8,7,11,10,12,9,10,8,8,6,8,7,11,10 ,11,12,8,8,11,11,10,9,10,10,5,5,9,9,10,8,11,10,11, 7,8,11,12,9,11,10,10,6,9,9,10,8,11,10,10,7,9,9,10, 8,9,9,9,2

The puzzle is simple: find an expression that generates the sequence.

There’s only one rule: the answer can’t be a degree 511 polynomial that generates these 512 values. You’re welcome to post this answer just to show off your (or your computer’s

) polynomial fitting skills, but it won’t count as a win.

Hints:

The sequence isn’t (to the best of my knowledge) generatable by a simple polynomial
I generated it using
- A generalization of the coefficients of the expected values in this post
- Something involving base 2 (binary) numbers
If you know the answer, you’d almost certainly know how to generate the sequence that begins with the following 512 numbers:
1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3, 3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3, 4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4, 3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3, 4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6, 6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4, 5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3, 4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4, 4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6, 7,6,7,7,8,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4, 3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4, 5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4, 4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6, 7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7, 5,6,6,7,6,7,7,8,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3, 4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5, 5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,4, 5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7, 6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6, 7,7,8,6,7,7,8,7,8,8,9,1

modest · 06-30-2009

Frustrating. [edit: In a good way

]

I figured out the second sequence, but I can't figure out a way to make an expression of it. For the integer 10:

A(2⁰)+B(2¹)+C(2²)+D(2³)

I realize what A, B, C, and D represent as it relates to binary numbers (that A and C should be zero while B and D are one), but I cannot figure out how to make an expression realize it.

I would think A somehow represents that 10/2 has a remainder of zero, B that 5/2 has r=1, C that 2/2 has r=0, and D that 1/2 has r=1.

That's a guess, and I'm stuck.

~modest

CraigD · 07-02-2009

Here’s an example of a sequence generated using only the first 100 integers and the “something involving base 2 (binary) numbers” part of the algorithm used to generate the puzzle sequence:
1
1
2 1
2 2 3 1
2 2 3 2 3 3 4 1
2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1
2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 1
2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 2 3 3 4 3

modest · 07-11-2009

Could you verify that I have interpreted your second sequence correctly? (I dare not say: usefully) That is, summing the digits in a binary count

base 10 = binary => binary sum = digit in sequence
1 = 1 => 1 = 1
2 = 10 => 1+0 = 1
3 = 11 => 1+1 = 2
4 = 100 => 1+0+0 = 1
5 = 101 => 1+0+1 = 2
6 = 110 => 1+1+0 = 2
7 = 111 => 1+1+1 = 3
8 = 1000 => 1+0+0+0 = 1
9 = 1001 => 1+0+0+1 = 2
10 = 1010 => 1+0+1+0 = 2

gives the sequence 1,1,2,1,2,2,3,1,2,2... For which you say “If you know the answer, you’d almost certainly know how to generate the sequence that begins with the following 512 numbers:”. If this is indeed the way the second sequence was meant to be interpreted then you could perhaps give a nod.

~modest

CraigD · 07-11-2009

Quote:

Originally Posted by modest

Could you verify that I have interpreted your second sequence correctly?

Yes, you have.

I’m honestly not sure if anyone short of an intuitive mathematical genius (not that I’m suggesting modest, or any other member, isn’t

) could guess the next parts of the puzzle without my post #1 clue linking to this post, so modest or any other puzzler, please don't feel restrained in followin it, unless you're committed to an excercise in intuition, or some formal method beyond my comprehension.

In the interest of not excessively teasing at the puzzle, I’ll throw out another clue: rational numbers.

Turtle · 07-12-2009

Quote:

Originally Posted by CraigD

Yes, you have.

I’m honestly not sure if anyone short of an intuitive mathematical genius (not that I’m suggesting modest, or any other member, isn’t

) could guess the next parts of the puzzle without my post #1 clue linking to this post, so modest or any other puzzler, please don't feel restrained in followin it, unless you're committed to an excercise in intuition, or some formal method beyond my comprehension.

In the interest of not excessively teasing at the puzzle, I’ll throw out another clue: rational numbers.

i would never have seen that!

still, it wasn't for a lack of looking.

anyway, i keep looking at your 'clue' post & either i'm missing something even more obvious or you have made an error. to whit:

Quote:

Originally Posted by Craig

For example, the expected value of a fair 6-sided die roll is
$1\frac16+2\frac16+3\frac16+4\frac16+5\frac16+6\frac16 = \frac{21}6 = 3.5$
which can be confirmed by noting that, after many die roles, the average roll approaches 3.5

since $1\frac{1}6$ = $\frac{7}6$ and $2\frac{1}6$ = $\frac{13}6$ , aren't we already up to $\frac{20}6$ and with the 4 other terms aren't we at $\frac{95}6$ ?

CraigD · 07-12-2009

Quote:

Originally Posted by Turtle

.. anyway, i keep looking at your 'clue' post & either i'm missing something even more obvious or you have made an error. to whit:

Quote:

Originally Posted by Craig

For example, the expected value of a fair 6-sided die roll is
$1\frac16+2\frac16+3\frac16+4\frac16+5\frac16+6\frac16 = \frac{21}6 = 3.5$
which can be confirmed by noting that, after many die roles, the average roll approaches 3.5.

since $1\frac{1}6$ = $\frac{7}6$ and $2\frac{1}6$ = $\frac{13}6$ , aren't we already up to $\frac{20}6$ and with the 4 other terms aren't we at $\frac{95}6$ ?

I believe you’re missing the traditional algebraic implied multiplication operator, Turtle.

That is
$a\frac{b}{c}$
means
$a \cdot \frac{b}{c}$
, not
$a +\frac{b}{c}$
, as you’re reading it.

Turtle · 07-12-2009

Quote:

Originally Posted by CraigD

I believe you’re missing the traditional algebraic implied multiplication operator, Turtle.

That is
$a\frac{b}{c}$
means
$a \cdot \frac{b}{c}$
, not
$a +\frac{b}{c}$
, as you’re reading it.

roger. i'm back on it like an implied operator.

Turtle · 07-12-2009

computer was off, i was in bed, & on the verge of sleep, but something about Craig making his list the first 512 elements kept nagging me. so 512 is $2^9$ and in binary that's 1000000000. so, every power of 2 the sequence gets back to one and then repeats the last pattern until every element is used, then takes that same pattern again but adds 1 to every element. each new group contains $2^n-2^{n-1}$ more elements than the last. (mathspeak for every group is twice as big as the last.

) the separated line below in the code box is my addition of the next group, but it's not complete, but it's late & i'm outa steam.

Code:

1,
1,2,
1,2,2,3,
1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,

1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3, 4,4,5,4,5,5,6,4...

Turtle · 07-14-2009

yes? no? maybe?

An integer sequence puzzle

Hypography?

Share the love!

Sponsors

Friends