cp's OEIS Frontend

A109812 a(1)=1; thereafter a(n) = smallest positive integer not among the earlier terms of the sequence such that a(n) and a(n-1) have no common 1-bits in their binary representations.

%I A109812 #224 Sep 03 2023 15:01:20
%S A109812 1,2,4,3,8,5,10,16,6,9,18,12,17,14,32,7,24,33,20,11,36,19,40,21,34,13,
%T A109812 48,15,64,22,41,66,25,38,65,26,37,72,23,96,27,68,35,28,67,44,80,39,88,
%U A109812 128,29,98,129,30,97,130,45,82,132,42,69,50,73,52,74,49,70,56,71,136,51
%N A109812 a(1)=1; thereafter a(n) = smallest positive integer not among the earlier terms of the sequence such that a(n) and a(n-1) have no common 1-bits in their binary representations.
%C A109812 Theorem: Sequence is a permutation of the positive integers. - _Leroy Quet_, Aug 16 2005
%C A109812 Proof: It is clear that the sequence is infinite. The first time a number >= 2^k appears (for k>1), it must BE 2^k, and is therefore immediately followed by the smallest missing number. Since there are infinitely many powers of 2, every number will eventually appear. - _N. J. A. Sloane_, Jun 02 2018, rewritten Apr 03 2022
%C A109812 The sequence should really begin with a(0) = 0, a(1) = 1, a(2) = 2, etc., and be defined simply as "the lexicographically earliest infinite sequence of nonnegative numbers such that the binary expansions of adjacent terms are disjoint". There is also an obvious equivalent definition as a sequence of subsets of the nonnegative integers such that successive subsets are disjoint. But for historical reasons we will keep the present definition. - _N. J. A. Sloane_, Apr 04 2022
%C A109812 Inverse permutation = A113233; A113232 = a(a(n)). - _Reinhard Zumkeller_, Oct 19 2005
%C A109812 Sequence of fixed points, where a(n) = n, is A340016. - _Thomas Scheuerle_, Dec 24 2020
%C A109812 Comment from _Rémy Sigrist_, Apr 04 2022 [added by _N. J. A. Sloane_, Apr 06 2022]: (Start)
%C A109812 If we compare the log scatterplots of the even and odd bisections of this sequence, usually everything is scrambled, but on some large intervals the bisections appear as two parallel stripes.
%C A109812 On these intervals, for some constant k,
%C A109812 - one bisection has values of the form 2^k + something < 2^(k-1)
%C A109812 - the other bisection has values < 2^(k-1).
%C A109812 This is shown in the pair of Sigrist "The two bisections" links. (End)
%C A109812 Comment from _N. J. A. Sloane_, Apr 06 2022: (Start)
%C A109812 Near Gavarnie France there is a gap in the wall of the Pyrenees known as the Brèche de Roland. The graph of the present sequence shows a sequence of very similar gaps or brèches, at slightly irregular intervals.
%C A109812 It is hoped that if the positions of these brèches can be identified, this will provide a key to the structure of this mysterious sequence.
%C A109812 If the reader clicks the "graph" button here, the top graph shows an obvious brèche between n=59 and n=71. This is also shown in one of the links below.
%C A109812 [More information about the positions of the brèches will be added here soon.] (End)
%C A109812 If a(m) AND a(n) = a(m) then m <= n. - _Rémy Sigrist_, Apr 04 2022
%C A109812 It appears that a(n)/n is bounded (it is probably less than 4 for all n), and n/a(n) is unbounded. See A352336, A352359, A352917-A352923 and the conjectures therein. - _David Broadhurst_, Apr 17 2022
%C A109812 This is also a lookup-table for a strategy of the 2-player 2-heap misere-Nim game (where a winning position is indicated by a XOR Nim-sum of the 2 heaps equal to zero). See e.g. A048833. - _R. J. Mathar_, Apr 29 2022
%C A109812 The set-theory analog of A093714 is essentially the same sequence as this. The definition is: b(0)=0; thereafter b(n+1) = smallest missing nonnegative integer which is different from b(n)+1 and whose binary expansion has no 1-bit in common with the binary expansion of b(n). This begins 0, 2, 1, 4, 3, 8, ..., and b(n) = a(n) for n > 2. - _N. J. A. Sloane_, May 07 2022
%H A109812 Paul Tek, <a href="/A109812/b109812.txt">Table of n, a(n) for n = 1..10000</a>
%H A109812 Michael De Vlieger, <a href="/A109812/a109812.png">Log-log scatterplot of a(n)</a>, n = 1..2^20, showing "lakes" as a triangular void in each rank interval, and "breaks" (breche) that may or may not recur in the same location in each rank interval.
%H A109812 Michael De Vlieger, <a href="/A109812/a109812_1.png">Scatterplot of a(n)</a>, n = 1..2^20, with 1:1 aspect ratio.
%H A109812 Michael De Vlieger, <a href="/A109812/a109812_2.png">Scatterplot of a(n)</a>, n = 1..2^16, plotting even-indexed terms in red and odd in blue.
%H A109812 Michael De Vlieger, <a href="/A109812/a109812_3.png">Bitmap of a(n)</a>, n = 1..2^10, expanding terms vertically with least significant bit at bottom, showing 1's in black and 0's in white. 12X vertical exaggeration.
%H A109812 Michael De Vlieger, <a href="/A109812/a109812_4.png">Bitmap of a(n)</a>, n = 1..2^14, expanding terms horizontally with least significant bit at right, showing 1's in black and 0's in white. 256X horizontal exaggeration (4096 X 16384 image size).
%H A109812 Michael De Vlieger, <a href="/A109812/a109812_5.png">Log-log scatterplot of a(n)</a>, n = 2^15..2^16-1, even-indexed terms in red, odd in blue, superimposed upon 2*a([n/2]), shown in large amber points, so as to explore "fractal" quality of the sequence.
%H A109812 Thomas Scheuerle, <a href="/A109812/a109812.svg">Graph of A109812 for n = 0..10^7</a>
%H A109812 Rémy Sigrist, <a href="/A109812/a109812_11.png">The two bisections of this sequence are shown in red and blue</a>. The arrows indicate places where the two bisections appear as parallel stripes (these are examples of brèches).
%H A109812 Rémy Sigrist, <a href="/A109812/a109812_12.png">The two bisections shown next to each other, alongside binary plots of the a(n)</a>
%H A109812 N. J. A. Sloane, <a href="/A352575/a352575.txt">Right-justified table of n, a(n) in binary, for n = 1..20000</a> [Copied from A352575]
%H A109812 N. J. A. Sloane, <a href="/A352575/a352575-1M.txt.gz">Right-justified table of n, a(n) in binary for n = 1..10^6</a> [gzipped file, copied from A352575] [This file was corrupted, but today I replaced it with a corrected version. - _N. J. A. Sloane_, Apr 11 2022]
%H A109812 N. J. A. Sloane, <a href="/A109812/a109812.pdf">The brèche between n = 59 and n = 70</a>
%H A109812 N. J. A. Sloane, <a href="https://vimeo.com/704569041/4ffa06b95e">The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems</a>, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: <a href="https://sites.math.rutgers.edu/~zeilberg/EM22/C27.pdf">Slides</a>; <a href="http://NeilSloane.com/doc/Math640.04.2022.pdf">Slides (an alternative source)</a>.
%H A109812 Walter Trump, <a href="/A109812/a109812_6.png">Log-log plot of first 22 blocks of powers of 2</a> [The logs are to base 2; the red lines are at powers of 2; for small n the points have been enlarged to make them visible; the x-axis shows values of n from 2^0 to 2^22]
%H A109812 Walter Trump, <a href="/A109812/a109812_7.png">Log-log plot of points a(n) for n from 2^19 to 2^25</a> [The logs are to base 2; the red lines are at powers of 2; the x-axis shows values of n from 2^19 to 2^25; the y-axis goes from 2^15 to 2^23]
%H A109812 Walter Trump, <a href="/A109812/a109812_8.png">Log-log plot of points a(n)/6 for n from 2^18 to 2^19</a>
%H A109812 Walter Trump, <a href="/A109812/a109812_9.png">Log-log plot of points a(n)/6 for n from 2^19 to 2^20</a>
%H A109812 Walter Trump, <a href="/A109812/a109812_10.png">Log-log plot of points a(n)/6 for n from 2^20 to 2^21</a>
%H A109812 Chai Wah Wu, <a href="/A109812/a109812.txt">Table of n, a(n) for n = 1..10^6</a>
%H A109812 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%H A109812 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A109812 It would be nice to have a formula or recurrence. - _N. J. A. Sloane_, Jun 02 2018
%F A109812 From _M. F. Hasler_, Apr 03 2022: (Start)
%F A109812 (1) If a(n) = 2^k and a(m) > 2^k then m > n: No term larger than 2^k can occur earlier than 2^k.
%F A109812 (2) For all k >= 0, a(n) = 2^k for some n <= 2^k: Any power of two will occur, not later than immediately after all smaller numbers.
%F A109812 (3) If a(n) = 2^k, and S(k) = {x < 2^k | x <> a(j) for all j < n} is not empty (which seems to be the case for all k > 1), then a(n+1) = min S(k): The smallest number less than a power of two that does not occur before it must occur immediately after it.
%F A109812 (4) If a(n) = 2^k with n < 2^k (probably true for all k > 1), then a(n+1) = min {x | x <> a(j) for all j <= n}. (End)
%e A109812 a(6) = 5, which is 101 in binary. Of the terms not among (1,2,4,3,8,5), the earlier terms of the sequence, 10 (decimal) = 1010 (binary) is the smallest positive integer with no common 1-bits with the binary representation of 5.
%e A109812 Of the other positive integers not occurring earlier in the sequence (6 = 110 binary, 7 = 111 binary, 9 = 1001 binary), each has at least one 1-bit in common with 5 = 101 in binary.
%e A109812 So a(7) = 10.
%e A109812 To illustrate the formulas (3) & (4): The powers of two a(3) = 4, a(5) = 8, a(8) = 16, and a(15) = 32 are immediately followed by 3, 5, 6 and 7, respectively, which are the smallest numbers that did not occur earlier. - _M. F. Hasler_, Apr 03 2022
%p A109812 read(transforms) : # ANDnos def'd here
%p A109812 A109812 := proc(n)
%p A109812     option remember;
%p A109812     local c,i,known ;
%p A109812     if n = 1 then
%p A109812         1;
%p A109812     else
%p A109812         for c from 1 do
%p A109812             known := false ;
%p A109812             for i from 1 to n-1 do
%p A109812                 if procname(i) = c then
%p A109812                     known := true;
%p A109812                     break ;
%p A109812                 end if;
%p A109812             end do:
%p A109812             if not known and ANDnos(c,procname(n-1)) =0 then
%p A109812                 return c;
%p A109812             end if;
%p A109812         end do:
%p A109812     end if;
%p A109812 end proc:
%p A109812 seq(A109812(n),n=1..200) ; # _R. J. Mathar_, Mar 29 2022
%t A109812 nn = 71; c[_] = 0; a[1] = c[1] = 1; u = 2; Do[If[a[i - 1] == u, While[c[u] > 0, u++]]; k = u; While[Nand[c[k] == 0, BitAnd[a[i - 1], k] == 0], k++]; Set[{a[i], c[k]}, {k, i}], {i, 2, nn}]; Array[a, nn] (* _Michael De Vlieger_, Apr 05 2022 *)
%o A109812 (Haskell)
%o A109812 import Data.Bits ((.&.)); import Data.List (delete)
%o A109812 a109812 n = a109812_list !! (n-1)
%o A109812 a109812_list = f 0 [1..] :: [Int] where
%o A109812    f v ws = g ws where
%o A109812      g (x:xs) = if v .&. x == 0 then x : f x (delete x ws) else g xs
%o A109812 -- _Reinhard Zumkeller_, Sep 15 2014
%o A109812 (Python)
%o A109812 A109812_list, l1, s, b = [1], 1, 2, set()
%o A109812 for _ in range(10**6):
%o A109812     i = s
%o A109812     while True:
%o A109812         if not (i in b or i & l1):
%o A109812             A109812_list.append(i)
%o A109812             l1 = i
%o A109812             b.add(i)
%o A109812             while s in b:
%o A109812                 b.remove(s)
%o A109812                 s += 1
%o A109812             break
%o A109812         i += 1 # _Chai Wah Wu_, Jun 04 2018
%o A109812 (PARI)
%o A109812 A109812_vec(n=100, a=0, U=[a])={vector(n, i, my(k=U[1]);
%o A109812 while(bitand(a, k++) || setsearch(U, k), );
%o A109812 if(k>U[1]+1, U=setunion(U, [k]), U[1]++); a=k)}
%o A109812 \\ _M. F. Hasler_, Apr 03 2022; corrected Apr 07 2022
%Y A109812 Cf. A115510, A113232, A113233, A113234, A340016, A352205, A352206, A352336, A352359, A352917-A352923, A353714.
%Y A109812 For positions of powers of 2 see A305370.
%Y A109812 Records: A352203, A352204; parity: A352569, A352570; written in binary: A352575.
%Y A109812 Partial sums: A352781.
%Y A109812 See also A093714, A305369, A352794.
%Y A109812 The graphs of A109812, A252867, A305369, A305372 (bisection) all have roughly the same, mysterious, fractal-like structure. - _N. J. A. Sloane_, Jun 03 2018
%K A109812 nonn,base,nice,look
%O A109812 1,2
%A A109812 _Leroy Quet_, Aug 16 2005
%E A109812 More terms from _John W. Layman_, Aug 18 2005
%E A109812 Edited by _N. J. A. Sloane_, Jun 02 2018