A308551 Start with an empty stack S; for n = 1, 2, 3, ..., interpret the binary representation of n from left to right as follows: in case of bit 1, push the number 1 on top of S, in case of bit 0, replace the two numbers on top of S with their sum; a(n) gives the number on top of S after processing n.

1, 2, 1, 3, 1, 2, 1, 4, 1, 3, 1, 3, 1, 2, 1, 5, 1, 12, 1, 4, 1, 2, 1, 4, 1, 3, 1, 3, 1, 2, 1, 6, 1, 15, 1, 23, 1, 2, 1, 5, 1, 4, 1, 4, 1, 2, 1, 5, 1, 4, 1, 4, 1, 2, 1, 4, 1, 3, 1, 3, 1, 2, 1, 7, 1, 19, 1, 30, 1, 2, 1, 47, 1, 57, 1, 5, 1, 2, 1, 6, 1, 20, 1, 5

Offset: 1

Author

Rémy Sigrist, Jun 07 2019

Keywords

• nonn
• base
• look

Comments

After processing n, S has A268289(n) elements, the sum of which is A000788(n).

Every positive integer appears infinitely many times in the sequence.

The sequence has the same shape when represented at different scales.

Examples

			The first terms, alongside the binary representation of n and the evolution of stack S, are:
  n  a(n)  bin(n)  S
  -  ----  ------  -------------------------------------------------
  1     1       1  () -> (1)
  2     2      10  (1) -> (1,1) -> (2)
  3     1      11  (2) -> (2,1) -> (2,1,1)
  4     3     100  (2,1,1) -> (2,1,1,1) -> (2,1,2) -> (2,3)
  5     1     101  (2,3) -> (2,3,1) -> (2,4) -> (2,4,1)
  6     2     110  (2,4,1) -> (2,4,1,1) -> (2,4,1,1,1) -> (2,4,1,2)
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8192
• Sean A. Irvine, Java program (github)
• Rémy Sigrist, PARI program
• Wikipedia, Stack (abstract data type)

Crossrefs

Cf. A000788, A020989, A268289.

Programs

Java

See Links section.

PARI

See Links section.

Formula

a(n) = 1 iff n is odd.

a(A020989(k)) = k + 1 for any k >= 0.

If n is in A014486, then a(n) = a(n-1) + A000120(n) = 1 + A000120(n). - Charlie Neder, Jun 07 2019