|
| |
|
|
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.
|
|
80
|
|
|
|
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, 48, 15, 64, 22, 41, 66, 25, 38, 65, 26, 37, 72, 23, 96, 27, 68, 35, 28, 67, 44, 80, 39, 88, 128, 29, 98, 129, 30, 97, 130, 45, 82, 132, 42, 69, 50, 73, 52, 74, 49, 70, 56, 71, 136, 51
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Theorem: Sequence is a permutation of the positive integers. - Leroy Quet, Aug 16 2005
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
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
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.
On these intervals, for some constant k,
- one bisection has values of the form 2^k + something < 2^(k-1)
- the other bisection has values < 2^(k-1).
This is shown in the pair of Sigrist "The two bisections" links. (End)
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.
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.
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.
[More information about the positions of the brèches will be added here soon.] (End)
If a(m) AND a(n) = a(m) then m <= n. - Rémy Sigrist, Apr 04 2022
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
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
|
|
|
LINKS
|
Michael De Vlieger, Log-log scatterplot of a(n), 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.
Michael De Vlieger, Scatterplot of a(n), n = 1..2^16, plotting even-indexed terms in red and odd in blue.
Michael De Vlieger, Bitmap of a(n), 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.
Michael De Vlieger, Bitmap of a(n), 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).
Michael De Vlieger, Log-log scatterplot of a(n), 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.
Walter Trump, Log-log plot of first 22 blocks of powers of 2 [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]
|
|
|
FORMULA
|
It would be nice to have a formula or recurrence. - N. J. A. Sloane, Jun 02 2018
(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.
(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.
(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.
(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)
|
|
|
EXAMPLE
|
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.
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.
So a(7) = 10.
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
|
|
|
MAPLE
|
read(transforms) : # ANDnos def'd here
option remember;
local c, i, known ;
if n = 1 then
1;
else
for c from 1 do
known := false ;
for i from 1 to n-1 do
if procname(i) = c then
known := true;
break ;
end if;
end do:
if not known and ANDnos(c, procname(n-1)) =0 then
return c;
end if;
end do:
end if;
end proc:
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(Haskell)
import Data.Bits ((.&.)); import Data.List (delete)
a109812 n = a109812_list !! (n-1)
a109812_list = f 0 [1..] :: [Int] where
f v ws = g ws where
g (x:xs) = if v .&. x == 0 then x : f x (delete x ws) else g xs
(Python)
A109812_list, l1, s, b = [1], 1, 2, set()
for _ in range(10**6):
i = s
while True:
if not (i in b or i & l1):
l1 = i
b.add(i)
while s in b:
b.remove(s)
s += 1
break
(PARI)
A109812_vec(n=100, a=0, U=[a])={vector(n, i, my(k=U[1]);
while(bitand(a, k++) || setsearch(U, k), );
if(k>U[1]+1, U=setunion(U, [k]), U[1]++); a=k)}
|
|
|
CROSSREFS
|
Cf. A115510, A113232, A113233, A113234, A340016, A352205, A352206, A352336, A352359, A352917-A352923, A353714.
For positions of powers of 2 see A305370.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
