cp's OEIS Frontend

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

%I A023758 #158 Feb 23 2025 15:14:18
%S A023758 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 A023758 120,124,126,127,128,192,224,240,248,252,254,255,256,384,448,480,496,
%U A023758 504,508,510,511,512,768,896,960,992,1008,1016,1020,1022,1023
%N A023758 Numbers of the form 2^i - 2^j with i >= j.
%C A023758 Numbers whose digits in base 2 are in nonincreasing order.
%C A023758 Might be called "nialpdromes".
%C A023758 Subset of A077436. Proof: Since a(n) is of the 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 A023758 Numbers whose binary representation contains no "01". - _Benoit Cloitre_, May 23 2004
%C A023758 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 A023758 From _Gary W. Adamson_, Jul 18 2008: (Start)
%C A023758 As a triangle by rows starting:
%C A023758    1;
%C A023758    2,  3;
%C A023758    4,  6,  7;
%C A023758    8, 12, 14, 15;
%C A023758   16, 24, 28, 30, 31;
%C A023758   ...,
%C A023758 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 A023758 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 A023758 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 A023758 From _Andres Cicuttin_, Apr 29 2016: (Start)
%C A023758 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 A023758 Examples: for a(n) represented by three bits
%C A023758              Binary
%C A023758 a(5)= 4   ->  100   last bit = 0
%C A023758 a(6)= 6   ->  110   first bit = 1 (inverted last bit of previous number)
%C A023758 a(7)= 7   ->  111
%C A023758 and for a(n) represented by four bits
%C A023758              Binary
%C A023758 a(8) = 8   -> 1000
%C A023758 a(9) = 12  -> 1100  last bit = 0
%C A023758 a(10)= 14  -> 1110  first bit = 1 (inverted last bit of previous number)
%C A023758 a(11)= 15  -> 1111
%C A023758 (End)
%C A023758 Powers of 2 represented in bases which are terms 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
%C A023758 Numbers k such that k = 2^(1 + A000523(k)) - 2^A007814(k). - _Daniel Starodubtsev_, Aug 05 2021
%C A023758 A002260(n) = v(a(n)/2^v(a(n))+1) and A002024(n) = A002260(n) + v(a(n)) where v is the dyadic valuation (i.e., A007814). - _Lorenzo Sauras Altuzarra_, Feb 01 2023
%H A023758 Reinhard Zumkeller, <a href="/A023758/b023758.txt">Table of n, a(n) for n = 1..10000</a> (first 5051 terms from T. D. Noe)
%H A023758 Andreas M. Hinz and Paul K. Stockmeyer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Hinz/hinz5.html">Precious Metal Sequences and Sierpinski-Type Graphs</a>, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
%H A023758 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 A023758 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Digit.html">Digit</a>.
%H A023758 Wikipedia, <a href="https://en.wikipedia.org/wiki/Ring_counter">Ring counter</a>.
%H A023758 <a href="/index/Ar#2-automatic">Index entries for 2-automatic sequences</a>.
%H A023758 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.
%F A023758 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 A023758 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 A023758 For n > 0, a(n) mod 2 = A010054(n). - _Benoit Cloitre_, May 23 2004
%F A023758 A140130(a(n)) = 1 and for n > 1: A140129(a(n)) = A002262(n-2). - _Reinhard Zumkeller_, May 14 2008
%F A023758 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 A023758 Start with A000225. If k is in the sequence, then so is 2k. - _Ralf Stephan_, Aug 16 2013
%F A023758 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
%F A023758 A049502(a(n)) = 0. - _Reinhard Zumkeller_, Jun 17 2015
%F A023758 a(n) = a(n-1) + a(n-d)/a(d*(d+1)/2 + 2) if n > 1, d > 0, where d = A002262(n-2). - _Yuchun Ji_, May 11 2020
%F A023758 A277699(a(n)) = a(n)^2, A306441(a(n)) = a(n+1). - _Antti Karttunen_, Feb 15 2021 (the latter identity from A306441)
%F A023758 Sum_{n>=2} 1/a(n) = A211705. - _Amiram Eldar_, Feb 20 2022
%e A023758 a(22) = 64 = 32 + 32 = 2^5 + a(16) = 2^A003056(20) + a(22-5-1).
%e A023758 a(23) = 96 = 64 + 32 = 2^6 + a(16) = 2^A003056(21) + a(23-6-1).
%e A023758 a(24) = 112 = 64 + 48 = 2^6 + a(17) = 2^A003056(22) + a(24-6-1).
%p A023758 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 A023758 Union[Flatten[Table[2^i - 2^j, {i, 0, 100}, {j, 0, i}]]] (* _T. D. Noe_, Mar 15 2011 *)
%t A023758 Select[Range[0, 2^10], NoneTrue[Differences@ IntegerDigits[#, 2], # > 0 &] &] (* _Michael De Vlieger_, Sep 05 2017 *)
%o A023758 (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 A023758 (PARI) A023758(n)= my(r=round(sqrt(2*n--))); (1<<(n-r*(r-1)/2)-1)<<(r*(r+1)/2-n)
%o A023758 /* or, to illustrate the "decreasing digit" property and analogy to A064222: */
%o A023758 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 A023758 (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 A023758 (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 A023758 (Haskell)
%o A023758 import Data.Set (singleton, deleteFindMin, insert)
%o A023758 a023758 n = a023758_list !! (n-1)
%o A023758 a023758_list = 0 : f (singleton 1) where
%o A023758 f s = x : f (if even x then insert z s' else insert z $ insert (z+1) s')
%o A023758 where z = 2*x; (x, s') = deleteFindMin s
%o A023758 -- _Reinhard Zumkeller_, Sep 24 2014, Dec 19 2012
%o A023758 (Python)
%o A023758 def a_next(a_n): return (a_n | (a_n >> 1)) + (a_n & 1)
%o A023758 a_n = 1; a = [0]
%o A023758 for i in range(55): a.append(a_n); a_n = a_next(a_n) # _Falk Hüffner_, Feb 19 2022
%o A023758 (Python)
%o A023758 from math import isqrt
%o A023758 def A023758(n): return (1<<(m:=isqrt(n-1<<3)+1>>1))-(1<<(m*(m+1)-(n-1<<1)>>1)) # _Chai Wah Wu_, Feb 23 2025
%Y A023758 A000337(r) = sum of row T(r, c) with 0 <= c < r. See also A002024, A003056, A140129, A140130, A221975.
%Y A023758 Cf. A007088, A130123, A101082 (complement), A340375 (characteristic function).
%Y A023758 This is the base-2 version of A064222. First differences are A057728.
%Y A023758 Subsequence of A077436, of A129523, of A277704, and of A333762.
%Y A023758 Subsequences: A043569 (nonzero even terms, or equally, nonzero terms doubled), A175332, A272615, A335431, A000396 (its even terms only), A324200.
%Y A023758 Positions of zeros in A049502, A265397, A277899, A284264.
%Y A023758 Positions of ones in A283983, A283989.
%Y A023758 Positions of nonzero terms in A341509 (apart from the initial zero).
%Y A023758 Positions of squarefree terms in A260443.
%Y A023758 Fixed points of A264977, A277711, A283165, A334666.
%Y A023758 Distinct terms in A340632.
%Y A023758 Cf. also A002024, A002260, A007814, A133797, A152449, A181666, A211705, A277699, A306441.
%Y A023758 Cf. also A309758, A309759, A309761 (for analogous sequences).
%K A023758 nonn,easy
%O A023758 1,3
%A A023758 _Olivier Gérard_
%E A023758 Definition changed by _N. J. A. Sloane_, Jan 05 2008