

A160855


a(n) is the smallest positive integer not occurring earlier in the sequence such that Sum_{k=1..n} a(k) written in binary contains binary n as a substring.


9



1, 3, 2, 6, 8, 4, 5, 11, 10, 24, 12, 13, 7, 9, 28, 17, 36, 14, 20, 46, 22, 44, 25, 18, 15, 16, 19, 21, 23, 26, 38, 33, 68, 30, 37, 29, 65, 39, 27, 57, 50, 88, 45, 85, 47, 83, 48, 34, 49, 51, 79, 53, 56, 32, 31, 35, 40, 41, 42, 63, 58, 72, 64, 66, 69, 61, 129, 93, 106, 60, 86
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Is this a permutation of the positive integers?
The smallest number not in {a(n)  n<=8000000} is 5083527. It appears that the quotient (a(1)+...+a(n))/n^2 meanders around between 1/2 (=perfect permutation) and 2/3: at n=8000000 the value is approximately 0.5866 (does it converge? 1/2? Golden ratio?).
The scatterplot of the first 100000 terms (see "graph") has some remarkable features which have not yet been explained.  Leroy Quet, Jul 05 2009
The lines that appear in the scatterplot seem to be related to the position of n in the sum of the first n terms; see colorized scatterplots in the Links section.  Rémy Sigrist, May 08 2017
From Michael De Vlieger, May 09 2017: (Start)
Starting positions of n in Sum_{k=1..n} a(k) written in binary: {1, 1, 1, 2, 1, 1, 1, 3, 2, 4, 3, 1, 1, 1, 5, 3, 2, 4, 3, 5, 4, 5, ...}.
Running total of a(n) in binary: {1, 100, 110, 1100, 10100, 11000, 11101, 101000, 110010, 1001010, 1010110, 1100011, 1101010, 1110011, ...}.
(End)


LINKS

H. v. Eitzen, Table of n, a(n) for n=1..100000
Rémy Sigrist, Colorized scatterplot of the first 100000 terms
Rémy Sigrist, Alternate colorized scatterplot of the first 100000 terms


FORMULA

a(A236341(n)) = n.  Reinhard Zumkeller, Jul 12 2015


EXAMPLE

From Michael De Vlieger, May 09 2017: (Start)
a(1) = 1 since binary n = "1" appears in the binary total of all numbers in the sequence "1" at position 1.
a(2) = 3 since binary n = "10" appears in the binary total of all numbers in the sequence (1 + 3) = "100" starting at position 1.
a(3) = 2 since binary n = "11" appears in the binary total of all numbers in the sequence (1 + 3 + 2) = "110" starting at position 1.
a(4) = 6 since binary n = "100" appears in the binary total of all numbers in the sequence (1 + 3 + 2 + 6) = "1100" starting at position 2.
...
(End)


MATHEMATICA

a = {}; Do[k = 1; While[Or[MemberQ[a, k], SequencePosition[ IntegerDigits[Total@ a + k, 2], #] == {}], k++] &@ IntegerDigits[n, 2]; AppendTo[a, k], {n, 71}]; a (* Michael De Vlieger, May 09 2017, Version 10.1 *)


PROG

(Haskell)
import Data.List (delete)
a160855 n = a160855_list !! (n  1)
a160855_list = 1 : f 2 1 [2..] where
f x sum zs = g zs where
g (y:ys) = if binSub x (sum + y)
then y : f (x + 1) (sum + y) (delete y zs) else g ys
binSub u = sub where
sub w = mod w m == u  w > u && sub (div w 2)
m = a062383 u
 Reinhard Zumkeller, Jul 12 2015


CROSSREFS

Cf. A160856.
Cf. A062383, A236341 (putative inverse).
Sequence in context: A193998 A209171 A348686 * A120232 A292961 A019444
Adjacent sequences: A160852 A160853 A160854 * A160856 A160857 A160858


KEYWORD

nonn,base,look


AUTHOR

Leroy Quet, May 28 2009


EXTENSIONS

Extended by Ray Chandler, Jun 15 2009


STATUS

approved



