13
$\begingroup$

What is the 30th number in the following sequence?

0, 2, 4, 12, 8, 20, 24, 56, 16, 36, ...

I'm not sure what would be good hints, or how much further out I should list the sequence. I figure the first ten values should be a good start, but I can add or confirm more if needed.

BTW, The first six are sufficient to show that this sequence does not appear on the Online Encyclopedia of Integer Sequences.

$\endgroup$
  • 1
    $\begingroup$ There are an infinite number of justifiable solutions. $\endgroup$ – OrangeDog May 19 '16 at 12:48
26
$\begingroup$

I would say that the 30th number in the sequence is:

$464$

Explanation:

Let $H(n)$ be the Hamming weight of a number $n$, where the Hamming weight is the sum of all the 1s in the binary representation of $n$.

Starting with $n = 0$, each number in the sequence $S(n)$ is $n \times 2^{H(n)}$.

For example, for $n = 5$, the binary representation of $5$ is $101$, and $H(5)$ is $2$. Thus the 6th element in the sequence is $5 \times 2^2 = 20. $

By this logic, the 30th element of the sequence has $n = 29$. The binary representation of $29$ is $11101$, so $H(29)$ is $4$. Thus the 30th element is $29 \times 2^4 = 464$.

$\endgroup$
  • $\begingroup$ Googling the sequence also worked :) $\endgroup$ – PierreDuc Apr 20 '16 at 13:35
  • 2
    $\begingroup$ How did you arrive at this? $\endgroup$ – question_asker Apr 20 '16 at 16:24
  • $\begingroup$ @PierreDuc Nothing useful comes up when I google the sequence (I get the sequence but no information on how it was arrived at) $\endgroup$ – question_asker Apr 20 '16 at 17:37
  • $\begingroup$ @question_asker Googling "0, 2, 4, 12, 8, 20, 24, 56, 16, 36" (with quotes) gave me http://webhome.cs.uvic.ca/~dmaslov/hwb9.txt... if you then go to http://webhome.cs.uvic.ca/~dmaslov/ and search for hwb9 you find: Hidden weighted bit functions :D $\endgroup$ – PierreDuc Apr 20 '16 at 17:48
  • 5
    $\begingroup$ @question_asker I just sort of noticed that each number S(n) in the sequence was divisible by n itself (it jumped out at me that 56 was 7*8, 24 was 6*4, 20 was 5*4, etc.) so I divided each term by it's "index" in the list and was left with 2 2 4 2 4 4 8 2 4 ... Obviously all being powers of 2, so I looked at them in binary and noticed the pattern. $\endgroup$ – SQLnoob Apr 20 '16 at 18:30
2
$\begingroup$

I would say that the 30th number in the sequence is:

28141044420

Explanation:

With the function : $f(x) = \frac{127 x^9}{20160}-\frac{251 x^8}{1008}+\frac{5957 x^7}{1440}-\frac{6757 x^6}{180}+\frac{582289 x^5}{2880}-\frac{94475 x^4}{144}+\frac{693097 x^3}{560}-\frac{170819 x^2}{140}+472 x$ See it on Wolfsram Alpha Starting with $n = 0$, each number in the sequence $S(n)$ is $f(n)$.
By this logic, the 30th element of the sequence has $n = 29$. Thus the 30th element is $f(29) = 28141044420$.

$\endgroup$
  • $\begingroup$ How on earth did you figure this out?! I can't even figure out if it makes sense, but if it does, it's amazing if you did it without complete automation. $\endgroup$ – SendersReagent Apr 20 '16 at 17:40
  • 4
    $\begingroup$ @SendersReagent Likely by fitting a polynomial to the sequence (solving for $a_i$ in $f(x) = a_1 x + \ldots + a_9 x^9$ - we have 9 unknowns and 9 equations so there is always a solution). This is very likely not the answer OP is thinking of but it illustrates the mathematical ambiguity in defining a sequence solely by the first $N$ terms: there are infinitely many functions that can match this. $\endgroup$ – Winther Apr 20 '16 at 17:53
1
$\begingroup$

Answer

116

Explanation

$f(0) = 0, f(1) = 2, f(2) = 4, f(3) = 12, f(4) = 8, f(5) = 20...$

$f(k) = 2 * k$, if $k = 2^x$ see that $f(2) = 4, f(4) = 8, f(8) = 16$
$f(k) = k * (k+1)$, if $k + 1 = 2^x$ see that $f(1) = 1*2, f(3) = 3*4, f(7) = 7 * 8$ $f(k) = k * 4$ otherwise
The 30th element is $f(29)$ so $f(29) = 29 * 4 = 116$ because $29 ≠ 2^x$ and $30 ≠ 2^x$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.