login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A023758 Numbers of the form 2^i - 2^j with i >= j. 44

%I

%S 0,1,2,3,4,6,7,8,12,14,15,16,24,28,30,31,32,48,56,60,62,63,64,96,112,

%T 120,124,126,127,128,192,224,240,248,252,254,255,256,384,448,480,496,

%U 504,508,510,511,512,768,896,960,992,1008,1016,1020,1022,1023

%N Numbers of the form 2^i - 2^j with i >= j.

%C Numbers whose digits in base 2 are in nonincreasing order.

%C Might be called "nialpdromes".

%C Subset of A077436. Proof: Since a(n) is of form (2^i-1)2^j, i,j>=0, a(n)^2 = [2^(2i)-2^(i+1)]2^(2j) + 2^(2j) where the first sum term has i-1 one bits and its 2j-th bit is zero, while the second sum term switches the 2j-th bit to one, giving i one bits, as in a(n). - _Ralf Stephan_, Mar 08 2004

%C Numbers n such that binary representation contains no "01". - _Benoit Cloitre_, May 23 2004

%C Every polynomial with coefficients equal to 1 for the leading terms and 0 after that, evaluated at 2. For instance a(13) = x^4 + x^3 + x^2 at 2, a(14) = x^4 + x^3 + x^2 + x at 2. - _Ben Paul Thurston_, Jan 11 2008

%C From _Gary W. Adamson_, Jul 18 2008: (Start)

%C As a triangle by rows starting:

%C 1;

%C 2, 3;

%C 4, 6, 7;

%C 8, 12, 14, 15;

%C 16, 24, 28, 30, 31;

%C ...,

%C equals A000012 * A130123 * A000012, where A130123 = (1, 0,2; 0,0,4; 0,0,0,8;...). Row sums of this triangle = A000337 starting (1, 5, 17, 49, 129, ...). (End)

%C First differences are A057728 = 1; 1; 1; 1; 2,1; 1; 4,2,1; 1; 8,4,2,1; 1;... i.e., decreasing powers of 2, separated by another "1". - _M. F. Hasler_, May 06 2009

%C Apart from first term, numbers that are powers of 2 or the sum of some consecutive powers of 2. - _Omar E. Pol_, Feb 14 2013

%C A049502(a(n)) = 0. - _Reinhard Zumkeller_, Jun 17 2015

%C From _Andres Cicuttin_, Apr 29 2016: (Start)

%C Numbers that can be digitally generated with twisted ring (Johnson) counters. This is, the binary digits of a(n) correspond to those stored in a shift register where the input bit of the first bit storage element is the inverted output of the last storage element. After starting with all 0’s, each new state is obtained by rotating the stored bits but inverting at each state transition the last bit that goes to the first position (see link).

%C Examples: for a(n) represented by three bits

%C Binary

%C a(5)= 4 -> 100 last bit = 0

%C a(6)= 6 -> 110 first bit = 1 (inverted last bit of previous number)

%C a(7)= 7 -> 111

%C and for a(n) represented by four bits

%C Binary

%C a(8) = 8 -> 1000

%C a(9) = 12 -> 1100 last bit = 0

%C a(10)= 14 -> 1110 first bit = 1 (inverted last bit of previous number)

%C a(11)= 15 -> 1111

%C (End)

%C Powers of 2 represented in bases which are members of this sequence must always contain at least one digit which is also a power of 2. This is because 2^i mod (2^i - 2^j) = 2^j, which means the last digit always cycles through powers of 2 (or if i=j+1 then the first digit is a power of 2 and the rest are trailing zeros). The only known non-member of this sequence with this property is 5. - _Ely Golden_, Sep 05 2017

%H T. D. Noe and R. Zumkeller, <a href="/A023758/b023758.txt">Table of n, a(n) for n = 1..10000</a>, First 5051 terms from T. D. Noe

%H S. M. Shabab Hossain, Md. Mahmudur Rahman and M. Sohel Rahman, <a href="http://dx.doi.org/10.1007/978-3-642-22494-2_4">Solving a Generalized Version of the Exact Cover Problem with a Light-Based Device</a>, Optical Supercomputing, Lecture Notes in Computer Science, 2011, Volume 6748/2011, 23-31, DOI: 10.1007/978-3-642-22494-2_4.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Digit.html">Digit</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Ring_counter">Ring counter</a>

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

%F a(n) = 2^s(n) - 2^((s(n)^2 + s(n) - 2n)/2) where s(n) = ceiling((-1 + sqrt(1+8n))/2). - _Sam Alexander_, Jan 08 2005

%F a(n) = 2^k + a(n-k-1) for 1 < n and k = A003056(n-2). The rows of T(r, c) = 2^r-2^c for 0 <= c < r read from right to left produce this sequence: 1; 2, 3; 4, 6, 7; 8, 12, 14, 15; ... - _Frank Ellermann_, Dec 06 2001

%F For n > 0, a(n) mod 2 == A010054(n). - _Benoit Cloitre_, May 23 2004

%F A140130(a(n)) = 1 and for n > 1: A140129(a(n)) = A002262(n-2). - _Reinhard Zumkeller_, May 14 2008

%F a(n+1) = (2^(n - r(r-1)/2) - 1) 2^(r(r+1)/2 - n), where r=round(sqrt(2n)). - _M. F. Hasler_, May 06 2009

%F Start with A000225. If n is in sequence, then so is 2n. - _Ralf Stephan_, Aug 16 2013

%F G.f.: (x^2/((2-x)*(1-x)))*(1 + Sum_{k>=0} x^((k^2+k)/2)*(1 + x*(2^k-1))). The sum is related to Jacobi theta functions. - _Robert Israel_, Feb 24 2015

%e a(22) = 64 = 32 + 32 = 2^5 + a(16) = 2^A003056(20) + a(22-5-1).

%e a(23) = 96 = 64 + 32 = 2^6 + a(16) = 2^A003056(21) + a(23-6-1).

%e a(24) = 112 = 64 + 48 = 2^6 + a(17) = 2^A003056(22) + a(24-6-1).

%p a:=proc(n) local n2,d: n2:=convert(n,base,2): d:={seq(n2[j]-n2[j-1],j=2..nops(n2))}: if n=0 then 0 elif n=1 then 1 elif d={0,1} or d={0} or d={1} then n else fi end: seq(a(n),n=0..2100); # _Emeric Deutsch_, Apr 22 2006

%t Union[Flatten[Table[2^i - 2^j, {i, 0, 100}, {j, 0, i}]]] (* _T. D. Noe_, Mar 15 2011 *)

%t Select[Range[0, 2^10], NoneTrue[Differences@ IntegerDigits[#, 2], # > 0 &] &] (* _Michael De Vlieger_, Sep 05 2017 *)

%o (PARI) for(n=0,2500,if(prod(k=1,length(binary(n))-1,component(binary(n),k)+1-component(binary(n),k+1))>0,print1(n,",")))

%o (PARI) A023758(n)= my(r=round(sqrt(2*n--))); (1<<(n-r*(r-1)/2)-1)<<(r*(r+1)/2-n)

%o /* or, to illustrate the "decreasing digit" property and analogy to A064222: */

%o A023758(n,show=0)={ my(a=0); while(n--, show & print1(a","); a=vecsort(binary(a+1)); a*=vector(#a,j,2^(j-1))~); a} \\ _M. F. Hasler_, May 06 2009

%o (PARI) is(n)=if(n<5,1,n>>=valuation(n,2);n++;n>>valuation(n,2)==1) \\ _Charles R Greathouse IV_, Jan 04 2016

%o (PARI) list(lim)=my(v=List([0]),t); for(i=1,logint(lim\1+1,2), t=2^i-1; while(t<=lim, listput(v,t); t*=2)); Set(v) \\ _Charles R Greathouse IV_, May 03 2016

%o (Haskell)

%o import Data.Set (singleton, deleteFindMin, insert)

%o a023758 n = a023758_list !! (n-1)

%o a023758_list = 0 : f (singleton 1) where

%o f s = x : f (if even x then insert z s' else insert z $ insert (z+1) s')

%o where z = 2*x; (x, s') = deleteFindMin s

%o -- _Reinhard Zumkeller_, Sep 24 2014, Dec 19 2012

%Y A000337(r) = sum of row T(r, c) with 0 <= c < r. See also A003056.

%Y Cf. A130123, A175332, A007088, A049502, A101082 (complement).

%Y This is the base-2 version of A064222. First differences are A057728.

%K nonn,easy

%O 1,3

%A _Olivier Gérard_

%E Definition changed by _N. J. A. Sloane_, Jan 05 2008

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 23 16:52 EDT 2019. Contains 321432 sequences. (Running on oeis4.)