cp's OEIS Frontend

A048645 Integers with one or two 1-bits in their binary expansion.

%I A048645 #119 Feb 16 2025 08:32:40
%S A048645 1,2,3,4,5,6,8,9,10,12,16,17,18,20,24,32,33,34,36,40,48,64,65,66,68,
%T A048645 72,80,96,128,129,130,132,136,144,160,192,256,257,258,260,264,272,288,
%U A048645 320,384,512,513,514,516,520,528,544,576,640,768,1024,1025,1026,1028,1032
%N A048645 Integers with one or two 1-bits in their binary expansion.
%C A048645 Apart from initial 1, sums of two not necessarily distinct powers of 2.
%C A048645 4 does not divide C(2s-1,s) (= A001700[ s ]) if and only if s=a(n).
%C A048645 Possible number of sides of a regular polygon such that there exists a triangulation where each triangle is isosceles. - _Sen-peng Eu_, May 07 2008
%C A048645 Also numbers n such that n!/2^(n-2) is an integer. - _Michel Lagneau_, Mar 28 2011
%C A048645 It appears these are also the indices of the terms that are shared by the cellular automata of A147562, A162795, A169707. - _Omar E. Pol_, Feb 21 2015
%C A048645 Numbers with binary weight 1 or 2. - _Omar E. Pol_, Feb 22 2015
%H A048645 Reinhard Zumkeller, <a href="/A048645/b048645.txt">Rows n = 1..100 of triangle, flattened</a>
%H A048645 Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, <a href="https://www.preprints.org/manuscript/202409.1581">Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds</a>, Preprints.org (2025).
%H A048645 Michael P. Connolly, <a href="https://research.manchester.ac.uk/en/studentTheses/probabilistic-rounding-error-analysis-for-numerical-linear-algebr">Probabilistic rounding error analysis for numerical linear algebra</a>, Ph. D. Thesis, Univ. Manchester (UK, 2022). See p. 55.
%H A048645 USA Mathematical Olympiad, <a href="https://artofproblemsolving.com/wiki/index.php/2008_USAMO_Problems/Problem_4">Problem 4</a>, 2008.
%H A048645 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/AutomaticSet.html">Automatic Set</a>.
%H A048645 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BinomialCoefficient.html">Binomial Coefficient</a>.
%H A048645 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>.
%H A048645 <a href="/index/O#Olympiads">Index to sequences related to Olympiads and other Mathematical competitions</a>.
%F A048645 a(0) = 1, a(n) = (2^(trinv(n-1)-1) + 2^((n-1)-((trinv(n-1)*(trinv(n-1)-1))/2))), i.e., 2^A003056(n) + 2^A002262(n-1) (the latter sequence contains the definition of trinv).
%F A048645 Let Theta = Sum_{k >= 0} x^(2^k). Then Sum_{n>=1} x^a(n) = (Theta^2 + Theta + x)/2. - _N. J. A. Sloane_, Jun 23 2009
%F A048645 As a triangle, for n > 1, 1 < k <= n: T(n,1) = A173786(n-2,n-2) and T(n,k) = A173786(n-1,k-2). - _Reinhard Zumkeller_, Feb 28 2010
%F A048645 It appears that A147562(a(n)) = A162795(a(n)) = A169707(a(n)). - _Omar E. Pol_, Feb 19 2015
%F A048645 Sum_{n>=1} 1/a(n) = 2 + A179951. - _Amiram Eldar_, Jan 22 2022
%e A048645 From _Omar E. Pol_, Feb 18 2015: (Start)
%e A048645 Also, written as a triangle T(j,k), k >= 1, in which row lengths are the terms of A028310:
%e A048645    1;
%e A048645    2;
%e A048645    3,  4;
%e A048645    5,  6,  8;
%e A048645    9, 10, 12, 16;
%e A048645   17, 18, 20, 24, 32;
%e A048645   33, 34, 36, 40, 48, 64;
%e A048645   65, 66, 68, 72, 80, 96, 128;
%e A048645   ...
%e A048645 It appears that column 1 is A094373.
%e A048645 It appears that the right border gives A000079.
%e A048645 It appears that the first differences in every row that contains at least two terms give the first h-1 powers of 2, where h is the length of the row.
%e A048645 (End)
%p A048645 lincom:=proc(a,b,n) local i,j,s,m; s:={}; for i from 0 to n do for j from 0 to n do m:=a^i+b^j; if m<=n then s:={op(s),m} fi od; od; lprint(sort([op(s)])); end: lincom(2,2,1000); # _Zerinvary Lajos_, Feb 24 2007
%t A048645 Select[Range[2000], 1 <= DigitCount[#, 2, 1] <= 2&] (* _Jean-François Alcover_, Mar 06 2016 *)
%o A048645 (Haskell)
%o A048645 import Data.List (insert)
%o A048645 a048645 n k = a048645_tabl !! (n-1) !! (k-1)
%o A048645 a048645_row n = a048645_tabl !! (n-1)
%o A048645 a048645_tabl = iterate (\xs -> insert (2 * head xs + 1) $ map ((* 2)) xs) [1]
%o A048645 a048645_list = concat a048645_tabl
%o A048645 -- _Reinhard Zumkeller_, Dec 19 2012
%o A048645 (PARI) isok(n) = my(hw = hammingweight(n)); (hw == 1) || (hw == 2); \\ _Michel Marcus_, Mar 06 2016
%o A048645 (PARI) a(n) = if(n <= 2, return(n), n-=2); my(c = (sqrtint(8*n + 1) - 1) \ 2); 1 << c + 1 << (n - binomial(c + 1, 2)) \\ _David A. Corneth_, Jan 02 2019
%o A048645 (PARI) nxt(n) = msb = 1 << logint(n, 2); if(n == msb, n + 1, t = n - msb; n + t) \\ _David A. Corneth_, Jan 02 2019
%o A048645 (Python)
%o A048645 def ok(n): return 1 <= bin(n)[2:].count('1') <= 2
%o A048645 print([k for k in range(1033) if ok(k)]) # _Michael S. Branicky_, Jan 22 2022
%o A048645 (Python)
%o A048645 from itertools import count, islice
%o A048645 def agen(): # generator of terms
%o A048645     for d in count(0):
%o A048645         msb = 2**d
%o A048645         yield msb
%o A048645         for lsb in range(d):
%o A048645             yield msb + 2**lsb
%o A048645 print(list(islice(agen(), 60))) # _Michael S. Branicky_, Jan 22 2022
%o A048645 (Python)
%o A048645 from math import isqrt, comb
%o A048645 def A048645(n): return (1<<(m:=isqrt(n-1<<3)+1>>1)-1)+(1<<(n-2-comb(m,2))) if n>1 else 1 # _Chai Wah Wu_, Oct 30 2024
%Y A048645 Cf. A018900, A048623, A046097, A169707, A147562, A162795, A003056, A002262, A094373, A028310, A179951.
%K A048645 easy,nonn,base,tabl
%O A048645 1,2
%A A048645 _Antti Karttunen_, Jul 14 1999