login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A018900 Sum of two distinct powers of 2. 62

%I

%S 3,5,6,9,10,12,17,18,20,24,33,34,36,40,48,65,66,68,72,80,96,129,130,

%T 132,136,144,160,192,257,258,260,264,272,288,320,384,513,514,516,520,

%U 528,544,576,640,768,1025,1026,1028,1032,1040,1056,1088,1152,1280,1536,2049,2050,2052,2056,2064,2080,2112,2176,2304,2560,3072

%N Sum of two distinct powers of 2.

%C Appears to give all n such that 8 is the highest power of 2 dividing A005148 (n). General conjecture: numbers k such that 8^a is the highest power of 2 dividing A005148 (k) is the same sequence as numbers k such that k has exactly (a+1) 1's in its binary representation. - _Benoit Cloitre_, Jun 22 2002

%C Seen as a triangle read by rows, T(n,k) = 2^(k-1) + 2^n, 1 <= k <= n, the sum of the n-th row equals A087323(n). - _Reinhard Zumkeller_, Jun 24 2009

%C A073267(a(n)) = 2. - _Reinhard Zumkeller_, Mar 07 2012

%C Numbers whose base-2 sum of digits is 2. - _Tom Edgar_, Aug 31 2013

%C All odd terms are A000051. - _Robert G. Wilson v_, Jan 03 2014

%C A239708 holds the subsequence of terms m such that m - 1 is prime. - _Hieronymus Fischer_, Apr 20 2014

%H T. D. Noe and Hieronymus Fischer, <a href="/A018900/b018900.txt">Table of n, a(n) for n = 1..10000</a> [terms 1..1000 from T. D. Noe]

%H Michael Beeler, R. William Gosper, and Richard Schroeppel, <a href="https://dspace.mit.edu/handle/1721.1/6086">HAKMEM</a>, MIT Artificial Intelligence Laboratory report AIM-239, February 1972. Item 175 page 81 by Gosper for iterating. Also <a href="http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item175">HTML transcription</a>.

%H Tilman Piesk, <a href="http://commons.wikimedia.org/wiki/File:8_choose_2_array.svg">Square array in reverse binary</a>

%F a(n) = 2^trinv(n-1) + 2^((n-1)-((trinv(n-1)*(trinv(n-1)-1))/2)), i.e., 2^A002024(n)+2^A002262(n-1). - _Antti Karttunen_

%F a(n) = A059268(n-1) + A140513(n-1). A000120(a(n)) = 2. Complement of A161989. A151774(a(n)) = 1. - _Reinhard Zumkeller_, Jun 24 2009

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

%F a(n) = A057168(a(n-1)) for n>1 and a(1) = 3. - _Marc LeBrun_, Jan 01 2014

%F From _Hieronymus Fischer_, Apr 20 2014: (Start)

%F Formulas for a general parameter b according to a(n) = b^i + b^j, i>j>=0; b = 2 for this sequence.

%F a(n) = b^i + b^j, where i = floor((sqrt(8n - 1) + 1)/2), j = n - 1 - i*(i - 1)/2 [for a Smalltalk implementation see Prog section, method distinctPowersOf: b (2 versions)].

%F a(A000217(n)) = (b + 1)*b^(n-1) = b^n + b^(n-1).

%F a(A000217(n)+1) = 1 + b^(n+1).

%F a(n + 1 + floor((sqrt(8n - 1) + 1)/2)) = b*a(n).

%F a(n + 1 + floor(log_b(a(n)))) = b*a(n).

%F a(n + 1) = b^2/(b+1) * a(n) + 1, if n is a triangular number (s. A000217).

%F a(n + 1) = b*a(n) + (1-b)* b^floor((sqrt(8n - 1) + 1)/2), if n is not a triangular number.

%F The next term can also be calculated without using the index n. Let m be a term and i = floor(log_b(m)), then:

%F a(n + 1) = b*m + (1-b)* b^i, if floor(log_b(m/(b+1))) + 1 < i,

%F a(n + 1) = b^2/(b+1) * m + 1, if floor(log_b(m/(b+1))) + 1 = i.

%F Partial sum:

%F Sum_{k=1..n} a(k) = (((b-1)*(j+1)+i-1)*b^(i-j) + b)*b^j - i)/(b-1), where i = floor((sqrt(8n - 1) + 1)/2), j = n - 1 - i*(i - 1)/2.

%F Inverse:

%F For each sequence term m, the index n such that a(n) = m is determined by n := i*(i-1)/2 + j + 1, where i := floor(log_b(m)), j := floor(log_b(m - b^floor(log_b(m)))) [for a Smalltalk implementation see Prog section, method invertedDistinctPowersOf: b].

%F Inequalities:

%F a(n) <= (b+1)/b * b^floor(sqrt(2n)+1/2), equality holds for triangular numbers.

%F a(n) > b^floor(sqrt(2n)+1/2).

%F a(n) < b^sqrt(2n)*sqrt(b).

%F a(n) > b^sqrt(2n)/sqrt(b).

%F Asymptotic behavior:

%F lim sup a(n)/b^sqrt(2n) = sqrt(b).

%F lim inf a(n)/b^sqrt(2n) = 1/sqrt(b).

%F lim sup a(n)/b^(floor(sqrt(2n))) = b.

%F lim inf a(n)/b^(floor(sqrt(2n))) = 1.

%F lim sup a(n)/b^(floor(sqrt(2n)+1/2)) = (b+1)/b.

%F lim inf a(n)/b^(floor(sqrt(2n)+1/2)) = 1.

%F (End)

%F Sum_{n>=1} 1/a(n) = A179951. - _Amiram Eldar_, Oct 06 2020

%e From _Hieronymus Fischer_, Apr 27 2014: (Start)

%e a(1) = 3, since 2 = 2^1 + 2^0.

%e a(5) = 10, since 10 = 2^3 + 2^1.

%e a(10^2) = 16640

%e a(10^3) = 35184372089344

%e a(10^4) = 2788273714550169769618891533295908724670464 = 2.788273714550...*10^42

%e a(10^5) = 3.6341936214780344527466190...*10^134

%e a(10^6) = 4.5332938264998904048012398...*10^425

%e a(10^7) = 1.6074616084721302346802429...*10^1346

%e a(10^8) = 1.4662184497310967196301632...*10^4257

%e a(10^9) = 2.3037539289782230932863807...*10^13462

%e a(10^10) = 9.1836811272250798973464436...*10^42571

%e (End)

%t Select[ Range[ 1056 ], (Count[ IntegerDigits[ #, 2 ], 1 ]==2)& ]

%t Union[Total/@Subsets[2^Range[0,10],{2}]] (* _Harvey P. Dale_, Mar 04 2012 *)

%o (PARI) for(m=1,9,for(n=0,m-1,print1(2^m+2^n", "))) \\ _Charles R Greathouse IV_, Sep 09 2011

%o (PARI) is(n)=hammingweight(n)==2 \\ _Charles R Greathouse IV_, Mar 03 2014

%o (PARI) for(n=0,10^5,if(hammingweight(n)==2,print1(n,", "))); \\ _Joerg Arndt_, Mar 04 2014

%o (Haskell)

%o a018900 n = a018900_list !! (n-1)

%o a018900_list = elemIndices 2 a073267_list -- _Reinhard Zumkeller_, Mar 07 2012

%o (C)

%o unsigned hakmem175(unsigned x) {

%o unsigned s, o, r;

%o s = x & -x; r = x + s;

%o o = x ^ r; o = (o >> 2) / s;

%o return r | o;

%o }

%o unsigned A018900(int n) {

%o if (n == 1) return 3;

%o return hakmem175(A018900(n - 1));

%o } // _Peter Luschny_, Jan 01 2014

%o (Smalltalk)

%o distinctPowersOf: b

%o "Version 1: Answers the n-th number of the form b^i + b^j, i>j>=0, where n is the receiver.

%o b > 1 (b = 2, for this sequence).

%o Usage: n distinctPowersOf: 2

%o Answer: a(n)"

%o | n i j |

%o n := self.

%o i := (8*n - 1) sqrtTruncated + 1 // 2.

%o j := n - (i*(i - 1)/2) - 1.

%o ^(b raisedToInteger: i) + (b raisedToInteger: j)

%o [by _Hieronymus Fischer_, Apr 20 2014]

%o ------------

%o (Smalltalk)

%o distinctPowersOf: b

%o "Version 2: Answers an array which holds the first n numbers of the form b^i + b^j, i>j>=0, where n is the receiver. b > 1 (b = 2, for this sequence).

%o Usage: n distinctPowersOf: 2

%o Answer: #(3 5 6 9 10 12 ...) [first n terms]"

%o | k p q terms |

%o terms := OrderedCollection new.

%o k := 0.

%o p := b.

%o q := 1.

%o [k < self] whileTrue:

%o [[q < p and: [k < self]] whileTrue:

%o [k := k + 1.

%o terms add: p + q.

%o q := b * q].

%o p := b * p.

%o q := 1].

%o ^terms as Array

%o [by _Hieronymus Fischer_, Apr 20 2014]

%o ------------

%o (Smalltalk)

%o floorDistinctPowersOf: b

%o "Answers an array which holds all the numbers b^i + b^j < n, i>j>=0, where n is the receiver.

%o b > 1 (b = 2, for this sequence).

%o Usage: n floorDistinctPowersOf: 2

%o Answer: #(3 5 6 9 10 12 ...) [all terms < n]"

%o | a n p q terms |

%o terms := OrderedCollection new.

%o n := self.

%o p := b.

%o q := 1.

%o a := p + q.

%o [a < n] whileTrue:

%o [[q < p and: [a < n]] whileTrue:

%o [terms add: a.

%o q := b * q.

%o a := p + q].

%o p := b * p.

%o q := 1.

%o a := p + q].

%o ^terms as Array

%o [by _Hieronymus Fischer_, Apr 20 2014]

%o ------------

%o (Smalltalk)

%o invertedDistinctPowersOf: b

%o "Given a number m which is a distinct power of b, this method answers the index n such that there are uniquely defined i>j>=0 for which b^i + b^j = m, where m is the receiver; b > 1 (b = 2, for this sequence).

%o Usage: m invertedDistinctPowersOf: 2

%o Answer: n such that a(n) = m, or, if no such n exists, min (k | a(k) >= m)"

%o | n i j k m |

%o m := self.

%o i := m integerFloorLog: b.

%o j := m - (b raisedToInteger: i) integerFloorLog: b.

%o n := i * (i - 1) / 2 + 1 + j.

%o ^n

%o [by _Hieronymus Fischer_, Apr 20 2014]

%o (Python)

%o print([n for n in range(1, 3001) if bin(n)[2:].count("1")==2]) # _Indranil Ghosh_, Jun 03 2017

%o (Python)

%o A018900_list = [2**a+2**b for a in range(1,10) for b in range(a)] # _Chai Wah Wu_, Jan 24 2021

%Y Cf. A001969, A048639, A048645, A057168.

%Y Cf. A000217, A179951, A187813, A239708.

%Y Cf. A000079, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (Hamming weight = 1, 3, 4, ..., 9).

%Y Sum of base-b digits equal b: A226636 (b = 3), A226969 (b = 4), A227062 (b = 5), A227080 (b = 6), A227092 (b = 7), A227095 (b = 8), A227238 (b = 9), A052224 (b = 10). [_M. F. Hasler_, Dec 23 2016]

%K nonn,easy,nice,tabl,look

%O 1,1

%A Jonn Dalton (jdalton(AT)vnet.ibm.com), Dec 11 1996

%E Edited by _M. F. Hasler_, Dec 23 2016

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 April 16 05:26 EDT 2021. Contains 343030 sequences. (Running on oeis4.)