cp's OEIS Frontend

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.

%I A160855 #30 Jul 19 2021 01:20:35
%S A160855 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,
%T A160855 19,21,23,26,38,33,68,30,37,29,65,39,27,57,50,88,45,85,47,83,48,34,49,
%U A160855 51,79,53,56,32,31,35,40,41,42,63,58,72,64,66,69,61,129,93,106,60,86
%N 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.
%C A160855 Is this a permutation of the positive integers?
%C A160855 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?).
%C A160855 The scatterplot of the first 100000 terms (see "graph") has some remarkable features which have not yet been explained. - _Leroy Quet_, Jul 05 2009
%C A160855 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
%C A160855 From _Michael De Vlieger_, May 09 2017: (Start)
%C A160855 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, ...}.
%C A160855 Running total of a(n) in binary: {1, 100, 110, 1100, 10100, 11000, 11101, 101000, 110010, 1001010, 1010110, 1100011, 1101010, 1110011, ...}.
%C A160855 (End)
%H A160855 H. v. Eitzen, <a href="/A160855/b160855.txt">Table of n, a(n) for n=1..100000</a>
%H A160855 Rémy Sigrist, <a href="/A160855/a160855.png">Colorized scatterplot of the first 100000 terms</a>
%H A160855 Rémy Sigrist, <a href="/A160855/a160855_1.png">Alternate colorized scatterplot of the first 100000 terms</a>
%F A160855 a(A236341(n)) = n. - _Reinhard Zumkeller_, Jul 12 2015
%e A160855 From _Michael De Vlieger_, May 09 2017: (Start)
%e A160855 a(1) = 1 since binary n = "1" appears in the binary total of all numbers in the sequence "1" at position 1.
%e A160855 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.
%e A160855 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.
%e A160855 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.
%e A160855 ...
%e A160855 (End)
%t A160855 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 *)
%o A160855 (Haskell)
%o A160855 import Data.List (delete)
%o A160855 a160855 n = a160855_list !! (n - 1)
%o A160855 a160855_list = 1 : f 2 1 [2..] where
%o A160855    f x sum zs = g zs where
%o A160855      g (y:ys) = if binSub x (sum + y)
%o A160855                    then y : f (x + 1) (sum + y) (delete y zs) else g ys
%o A160855    binSub u = sub where
%o A160855       sub w = mod w m == u || w > u && sub (div w 2)
%o A160855       m = a062383 u
%o A160855 -- _Reinhard Zumkeller_, Jul 12 2015
%Y A160855 Cf. A160856.
%Y A160855 Cf. A062383, A236341 (putative inverse).
%K A160855 nonn,base,look
%O A160855 1,2
%A A160855 _Leroy Quet_, May 28 2009
%E A160855 Extended by _Ray Chandler_, Jun 15 2009