A309079 For any n > 0: consider the strictly increasing finite sequences of integers whose concatenation of terms, in binary and without leading zeros, equals that of n; a(n) is the minimal sum of the terms of such a finite sequence.

1, 2, 3, 4, 5, 3, 4, 8, 9, 10, 5, 5, 6, 7, 8, 16, 17, 18, 19, 6, 7, 8, 9, 9, 10, 11, 6, 7, 8, 9, 10, 32, 33, 34, 35, 36, 9, 10, 11, 10, 11, 12, 13, 14, 15, 11, 12, 17, 18, 19, 20, 7, 8, 9, 10, 11, 12, 13, 14, 8, 9, 10, 11, 64, 65, 66, 67, 68, 69, 70, 71, 12

Offset: 1

Author

Rémy Sigrist, Jul 11 2019

Keywords

• nonn
• base

Comments

Any integer appear in the sequence:

- for any m > 0 with binary expansion Sum_{k >= 0} b_k * 2^k,

- let n = (Sum_{k >= 0} b_k * 2^Sum_{j >= k} ((1+j) * b_j))/2,

- then a(n) = m,

- for example (in binary): a("1101000") = "1" + "10" + "1000" = "1011".

Examples

			The first terms, alongside the corresponding finite sequences, are:
  n   a(n)  bin(n)  bin(seq)
  --  ----  ------  --------
   1     1       1  (1)
   2     2      10  (10)
   3     3      11  (11)
   4     4     100  (100)
   5     5     101  (101)
   6     3     110  (1,10)
   7     4     111  (1,11)
   8     8    1000  (1000)
   9     9    1001  (1001)
  10    10    1010  (1010)
  11     5    1011  (10,11)
  12     5    1100  (1,100)
  13     6    1101  (1,101)
  14     7    1110  (1,110)
  15     8    1111  (1,111)
  16    16   10000  (10000)
  17    17   10001  (10001)
  18    18   10010  (10010)
  19    19   10011  (10011)
  20     6   10100  (10,100)
  21     7   10101  (10,101)
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..8192
• Rémy Sigrist, PARI program for A309079

Crossrefs

Cf. A000225, A143789, A164894.

Programs

PARI

See Links section.

Formula

a(n) <= n with equality iff n is a power of two or the binary concatenation of 2^k and m for some k >= 0 and m <= 2^k.

a(2*n) <= 2*a(n).

a(2*n + 1) <= 2*a(n) + 1.

a(A164894(k)) = A000225(k) for any k > 0.