|
|
A007931
|
|
Numbers that contain only 1's and 2's. Nonempty binary strings of length n in lexicographic order.
|
|
82
|
|
|
1, 2, 11, 12, 21, 22, 111, 112, 121, 122, 211, 212, 221, 222, 1111, 1112, 1121, 1122, 1211, 1212, 1221, 1222, 2111, 2112, 2121, 2122, 2211, 2212, 2221, 2222, 11111, 11112, 11121, 11122, 11211, 11212, 11221, 11222, 12111, 12112, 12121, 12122
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Numbers written in the dyadic system [Smullyan, Stillwell]. - _N. J. A. Sloane_, Feb 13 2019
Logic-binary sequence: prefix it by the empty word to have all binary words on the alphabet {1,2}.
The least binary word of length k is a(2^k - 1).
See Mathematica program for logic-binary sequence using (0,1) in place of (1,2); the sequence starts with 0,1,00,01,10. - _Clark Kimberling_, Feb 09 2012
a(n) is n written in base 2 where zeros are not allowed but twos are. The two distinct digits used are 1, 2 instead of 0, 1. To obtain this sequence from the "canonical" base 2 sequence with zeros allowed, just replace any 0 with a 2 and then subtract one from the group of digits situated on the left: (10-->2; 100-->12; 110-->22; 1000-->112; 1010-->122). - _Robin Garcia_, Jan 31 2014
For numbers made of only two different digits, see also A007088 (digits 0 & 1), A032810 (digits 2 & 3), A032834 (digits 3 & 4), A256290 (digits 4 & 5), A256291 (digits 5 & 6), A256292 (digits 6 & 7), A256340(digits 7 & 8), A256341 (digits 8 & 9), and A032804-A032816 (in other bases). Numbers with exactly two distinct (but unspecified) digits in base 10 are listed in A031955, for other bases in A031948-A031954. - _M. F. Hasler_, Apr 04 2015
The variant with digits {0, 1} instead of {1, 2} is obtained by deleting all initial digits in sequence A007088 (numbers written in base 2). - _M. F. Hasler_, Nov 03 2020
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 2. - From _N. J. A. Sloane_, Jul 26 2012
K. Atanassov, On the 97th, 98th and the 99th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 3, 89-93.
R. M. Smullyan, Theory of Formal Systems, Princeton, 1961.
John Stillwell, Reverse Mathematics, Princeton, 2018. See p. 90.
|
|
LINKS
|
|
|
FORMULA
|
To get a(n), write n+1 in base 2, remove initial 1, add 1 to all remaining digits: e.g., eleven (11) in base 2 is 1011; remove initial 1 and add 1 to remaining digits: a(10)=122. - _Clark Kimberling_, Mar 11 2003
Conversely, given a(n), to get n: subtract 1 from all digits, prefix with an initial 1, convert this binary number to base 10, subtract 1. E.g., a(6)=22 -> 11 -> 111 -> 7 -> 6. - _N. J. A. Sloane_, Jul 09 2012
a(n) = A053645(n+1)+A002275(A000523(n)) = a(n-2^b(n))+10^b(n) where b(n) = A059939(n) = floor(log_2(n+1)-1). - _Henry Bottomley_, Feb 14 2001
From _Hieronymus Fischer_, Jun 06 2012 and Jun 08 2012: (Start)
The formulas are designed to calculate base-10 numbers only using the digits 1 and 2.
a(n) = Sum_{j=0..m-1} (1 + b(j) mod 2)*10^j, where m = floor(log_2(n+1)), b(j) = floor((n+1-2^m)/(2^j)).
Special values:
a(k*(2^n-1)) = k*(10^n-1)/9, k= 1,2.
a(3*2^n-2) = (11*10^n-2)/9 = 10^n+2*(10^n-1)/9.
a(2^n-2) = 2*(10^(n-1)-1)/9, n>1.
Inequalities:
a(n) <= (10^log_2(n+1)-1)/9, equality holds for n=2^k-1, k>0.
a(n) > (2/10)*(10^log_2(n+1)-1)/9.
Lower and upper limits:
lim inf a(n)/10^log_2(n) = 1/45, for n --> infinity.
lim sup a(n)/10^log_2(n) = 1/9, for n --> infinity.
G.f.: g(x) = (1/(x(1-x)))*sum_{j=0..infinity} 10^j* x^(2*2^j)*(1 + 2 x^2^j)/(1 + x^2^j).
Also: g(x) = (1/(1-x))*(h_(2,0)(x) + h_(2,1)(x) - 2*h_(2,2)(x)), where h_(2,k)(x) = sum_{j>=0} 10^j*x^(2^(j+1)-1)*x^(k*2^j)/(1-x^2^(j+1)).
Also: g(x) = (1/(1-x)) sum_{j>=0} (1 - 3(x^2^j)^2 + 2(x^2^j)^3)*x^2^j*f_j(x)/(1-x^2^j), where f_j(x) = 10^j*x^(2^j-1)/(1-(x^2^j)^2). The f_j obey the recurrence f_0(x) = 1/(1-x^2), f_(j+1)(x) = 10x*f_j(x^2). (End)
|
|
EXAMPLE
|
Positive numbers may not start with 0 in the OEIS, otherwise this sequence would have been written as: 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, ...
From _Hieronymus Fischer_, Jun 06 2012: (Start)
a(10) = 122.
a(100) = 211212.
a(10^3) = 222212112.
a(10^4) = 1122211121112.
a(10^5) = 2111122121211112.
a(10^6) = 2221211112112111112.
a(10^7) = 11221112112122121111112.
a(10^8) = 12222212122221111211111112.
a(10^9) = 22122211221212211212111111112. (End)
|
|
MAPLE
|
# Maple program to produce the sequence:
a:= proc(n) local m, r, d; m, r:= n, 0;
while m>0 do d:= irem(m, 2, 'm');
if d=0 then d:=2; m:= m-1 fi;
r:= d, r
od; parse(cat(r))/10
end:
seq(a(n), n=1..100); # _Alois P. Heinz_, Aug 26 2016
# Maple program to invert this sequence: given a(n), it returns n. - _N. J. A. Sloane_, Jul 09 2012
invert7931:=proc(u)
local t1, t2, i;
t1:=convert(u, base, 10);
[seq(t1[i]-1, i=1..nops(t1))];
[op(%), 1];
t2:=convert(%, base, 2, 10);
add(t2[i]*10^(i-1), i=1..nops(t2))-1;
end;
|
|
MATHEMATICA
|
f[n_] := FromDigits[Rest@IntegerDigits[n + 1, 2] + 1]; Array[f, 42] (* _Robert G. Wilson v_ Sep 14 2006 *)
(* Next, A007931 using (0, 1) instead of (1, 2) *)
d[n_] := FromDigits[Rest@IntegerDigits[n + 1, 2] + 1]; Array[FromCharacterCode[ToCharacterCode[ToString[d[#]]] - 1] &, 100] (* _Peter J. C. Moses_, at request of _Clark Kimberling_, Feb 09 2012 *)
Flatten[Table[FromDigits/@Tuples[{1, 2}, n], {n, 5}]] (* _Harvey P. Dale_, Sep 13 2014 *)
|
|
PROG
|
(Haskell)
a007931 n = f (n + 1) where
f x = if x < 2 then 0 else (10 * f x') + m + 1
where (x', m) = divMod x 2
-- _Reinhard Zumkeller_, Oct 26 2012
(PARI) apply( {A007931(n)=fromdigits([d+1|d<-binary(n+1)[^1]])}, [1..44]) \\ _M. F. Hasler_, Nov 03 2020, replacing older code from Mar 26 2015
(PARI) /* inverse function */ apply( {A007931_inv(N)=fromdigits([d-1|d<-digits(N)], 2)+2<<logint(N, 10)-1}, [1, 2, 11, 12, 21, 22, 111]) \\ _M. F. Hasler_, Nov 09 2020
(Magma) [n: n in [1..100000] | Set(Intseq(n)) subset {1, 2}]; // _Vincenzo Librandi_, Aug 19 2016
(Python)
def a(n): return int(bin(n+1)[3:].replace('1', '2').replace('0', '1'))
print([a(n) for n in range(1, 45)]) # _Michael S. Branicky_, May 13 2021
|
|
CROSSREFS
|
Cf. A007932 (digits 1-3), A059893, A045670, A052382 (digits 1-9), A059939, A059941, A059943, A032924, A084544, A084545, A046034 (prime digits 2,3,5,7), A089581, A084984 (no prime digits); A001742, A001743, A001744: loops; A202267 (digits 0, 1 and primes), A202268 (digits 1,4,6,8,9), A014261 (odd digits), A014263 (even digits).
|
|
KEYWORD
|
nonn,base,nice,easy
|
|
AUTHOR
|
R. Muller
|
|
EXTENSIONS
|
Some crossrefs added by _Hieronymus Fischer_, Jun 06 2012
Edited by _M. F. Hasler_, Mar 26 2015
|
|
STATUS
|
approved
|
|
|
|