login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007931 Numbers that contain only 1's and 2's. Nonempty binary strings of length n in lexicographic order. 82

%I #134 Sep 08 2022 08:44:35

%S 1,2,11,12,21,22,111,112,121,122,211,212,221,222,1111,1112,1121,1122,

%T 1211,1212,1221,1222,2111,2112,2121,2122,2211,2212,2221,2222,11111,

%U 11112,11121,11122,11211,11212,11221,11222,12111,12112,12121,12122

%N Numbers that contain only 1's and 2's. Nonempty binary strings of length n in lexicographic order.

%C Numbers written in the dyadic system [Smullyan, Stillwell]. - _N. J. A. Sloane_, Feb 13 2019

%C Logic-binary sequence: prefix it by the empty word to have all binary words on the alphabet {1,2}.

%C The least binary word of length k is a(2^k - 1).

%C 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

%C A007953(a(n)) = A014701(n+1); A007954(a(n)) = A048896(n). - _Reinhard Zumkeller_, Oct 26 2012

%C 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

%C 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

%C 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

%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 2. - From _N. J. A. Sloane_, Jul 26 2012

%D 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.

%D R. M. Smullyan, Theory of Formal Systems, Princeton, 1961.

%D John Stillwell, Reverse Mathematics, Princeton, 2018. See p. 90.

%H Hieronymus Fischer, <a href="/A007931/b007931.txt">Table of n, a(n) for n = 1..10000</a> (terms up to 2^10-2 from T. D. Noe, corrected by Sean A. Irvine, April 18 2019)

%H K. Atanassov, <a href="http://www.gallup.unm.edu/~smarandache/Atanassov-SomeProblems.pdf">On Some of Smarandache's Problems</a>, American Research Press, 1999, 16-21.

%H EMIS, <a href="http://www.emis.de/journals/SWJPAM/vol1-95.html">Mirror site for Southwest Journal of Pure and Applied Mathematics</a>

%H R. R. Forslund, <a href="http://www.emis.de/journals/SWJPAM/Vol1_1995/rrf01.ps">A logical alternative to the existing positional number system</a>, Southwest Journal of Pure and Applied Mathematics, Vol. 1, 1995.

%H R. R. Forslund, <a href="http://my.tbaytel.net/~forslund/index.html">Positive Integer Pages</a>

%H James E. Foster, <a href="http://www.jstor.org/stable/3029479">A Number System without a Zero-Symbol</a>, Mathematics Magazine, Vol. 21, No. 1. (1947), pp. 39-41.

%H F. Smarandache, <a href="http://www.gallup.unm.edu/~smarandache/OPNS.pdf">Only Problems, Not Solutions!</a>.

%H <a href="/index/Ar#10-automatic">Index entries for 10-automatic sequences</a>.

%F 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

%F 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

%F 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

%F From _Hieronymus Fischer_, Jun 06 2012 and Jun 08 2012: (Start)

%F The formulas are designed to calculate base-10 numbers only using the digits 1 and 2.

%F 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)).

%F Special values:

%F a(k*(2^n-1)) = k*(10^n-1)/9, k= 1,2.

%F a(3*2^n-2) = (11*10^n-2)/9 = 10^n+2*(10^n-1)/9.

%F a(2^n-2) = 2*(10^(n-1)-1)/9, n>1.

%F Inequalities:

%F a(n) <= (10^log_2(n+1)-1)/9, equality holds for n=2^k-1, k>0.

%F a(n) > (2/10)*(10^log_2(n+1)-1)/9.

%F Lower and upper limits:

%F lim inf a(n)/10^log_2(n) = 1/45, for n --> infinity.

%F lim sup a(n)/10^log_2(n) = 1/9, for n --> infinity.

%F 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).

%F 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)).

%F 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)

%e 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, ...

%e From _Hieronymus Fischer_, Jun 06 2012: (Start)

%e a(10) = 122.

%e a(100) = 211212.

%e a(10^3) = 222212112.

%e a(10^4) = 1122211121112.

%e a(10^5) = 2111122121211112.

%e a(10^6) = 2221211112112111112.

%e a(10^7) = 11221112112122121111112.

%e a(10^8) = 12222212122221111211111112.

%e a(10^9) = 22122211221212211212111111112. (End)

%p # Maple program to produce the sequence:

%p a:= proc(n) local m, r, d; m, r:= n, 0;

%p while m>0 do d:= irem(m, 2, 'm');

%p if d=0 then d:=2; m:= m-1 fi;

%p r:= d, r

%p od; parse(cat(r))/10

%p end:

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Aug 26 2016

%p # Maple program to invert this sequence: given a(n), it returns n. - _N. J. A. Sloane_, Jul 09 2012

%p invert7931:=proc(u)

%p local t1,t2,i;

%p t1:=convert(u,base,10);

%p [seq(t1[i]-1,i=1..nops(t1))];

%p [op(%),1];

%p t2:=convert(%,base,2,10);

%p add(t2[i]*10^(i-1),i=1..nops(t2))-1;

%p end;

%t f[n_] := FromDigits[Rest@IntegerDigits[n + 1, 2] + 1]; Array[f, 42] (* _Robert G. Wilson v_ Sep 14 2006 *)

%t (* Next, A007931 using (0,1) instead of (1,2) *)

%t 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 *)

%t Flatten[Table[FromDigits/@Tuples[{1,2},n],{n,5}]] (* _Harvey P. Dale_, Sep 13 2014 *)

%o (Haskell)

%o a007931 n = f (n + 1) where

%o f x = if x < 2 then 0 else (10 * f x') + m + 1

%o where (x', m) = divMod x 2

%o -- _Reinhard Zumkeller_, Oct 26 2012

%o (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

%o (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

%o (Magma) [n: n in [1..100000] | Set(Intseq(n)) subset {1,2}]; // _Vincenzo Librandi_, Aug 19 2016

%o (Python)

%o def a(n): return int(bin(n+1)[3:].replace('1', '2').replace('0', '1'))

%o print([a(n) for n in range(1, 45)]) # _Michael S. Branicky_, May 13 2021

%Y 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).

%Y Cf. 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).

%Y Cf. A020450 (primes).

%K nonn,base,nice,easy

%O 1,2

%A R. Muller

%E Some crossrefs added by _Hieronymus Fischer_, Jun 06 2012

%E Edited by _M. F. Hasler_, Mar 26 2015

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)