A018900 Sums of two distinct powers of 2.
3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129, 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384, 513, 514, 516, 520, 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
Offset: 1
Examples
From _Hieronymus Fischer_, Apr 27 2014: (Start) a(1) = 3, since 3 = 2^1 + 2^0. a(5) = 10, since 10 = 2^3 + 2^1. a(10^2) = 16640 a(10^3) = 35184372089344 a(10^4) = 2788273714550169769618891533295908724670464 = 2.788273714550...*10^42 a(10^5) = 3.6341936214780344527466190...*10^134 a(10^6) = 4.5332938264998904048012398...*10^425 a(10^7) = 1.6074616084721302346802429...*10^1346 a(10^8) = 1.4662184497310967196301632...*10^4257 a(10^9) = 2.3037539289782230932863807...*10^13462 a(10^10) = 9.1836811272250798973464436...*10^42571 (End)
Links
- T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 1..10000 [terms 1..1000 from T. D. Noe]
- Michael Beeler, R. William Gosper, and Richard Schroeppel, HAKMEM, MIT Artificial Intelligence Laboratory report AIM-239, February 1972. Item 175 page 81 by Gosper for iterating. Also HTML transcription.
- Tilman Piesk, Square array in reverse binary
Crossrefs
Programs
-
C
unsigned hakmem175(unsigned x) { unsigned s, o, r; s = x & -x; r = x + s; o = x ^ r; o = (o >> 2) / s; return r | o; } unsigned A018900(int n) { if (n == 1) return 3; return hakmem175(A018900(n - 1)); } // Peter Luschny, Jan 01 2014 -
Haskell
a018900 n = a018900_list !! (n-1) a018900_list = elemIndices 2 a073267_list -- Reinhard Zumkeller, Mar 07 2012
-
Maple
a:= n-> (i-> 2^i+2^(n-1-i*(i-1)/2))(floor((sqrt(8*n-1)+1)/2)): seq(a(n), n=1..100); # Alois P. Heinz, Feb 01 2022
-
Mathematica
Select[ Range[ 1056 ], (Count[ IntegerDigits[ #, 2 ], 1 ]==2)& ] Union[Total/@Subsets[2^Range[0,10],{2}]] (* Harvey P. Dale, Mar 04 2012 *) -
PARI
for(m=1,9,for(n=0,m-1,print1(2^m+2^n", "))) \\ Charles R Greathouse IV, Sep 09 2011
-
PARI
is(n)=hammingweight(n)==2 \\ Charles R Greathouse IV, Mar 03 2014
-
PARI
for(n=0,10^5,if(hammingweight(n)==2,print1(n,", "))); \\ Joerg Arndt, Mar 04 2014
-
PARI
a(n)= my(t=sqrtint(n*8)\/2); 2^t + 2^(n-1-t*(t-1)/2); \\ Ruud H.G. van Tol, Nov 30 2024
-
Python
print([n for n in range(1, 3001) if bin(n)[2:].count("1")==2]) # Indranil Ghosh, Jun 03 2017 -
Python
A018900_list = [2**a+2**b for a in range(1,10) for b in range(a)] # Chai Wah Wu, Jan 24 2021
-
Python
from math import isqrt, comb def A018900(n): return (1<<(m:=isqrt(n<<3)+1>>1))+(1<<(n-1-comb(m,2))) # Chai Wah Wu, Oct 30 2024
-
Smalltalk
distinctPowersOf: b "Version 1: Answers the n-th number of the form b^i + b^j, i>j>=0, where n is the receiver. b > 1 (b = 2, for this sequence). Usage: n distinctPowersOf: 2 Answer: a(n)" | n i j | n := self. i := (8*n - 1) sqrtTruncated + 1 // 2. j := n - (i*(i - 1)/2) - 1. ^(b raisedToInteger: i) + (b raisedToInteger: j) [by Hieronymus Fischer, Apr 20 2014] ------------
-
Smalltalk
distinctPowersOf: b "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). Usage: n distinctPowersOf: 2 Answer: #(3 5 6 9 10 12 ...) [first n terms]" | k p q terms | terms := OrderedCollection new. k := 0. p := b. q := 1. [k < self] whileTrue: [[q < p and: [k < self]] whileTrue: [k := k + 1. terms add: p + q. q := b * q]. p := b * p. q := 1]. ^terms as Array [by Hieronymus Fischer, Apr 20 2014] ------------ -
Smalltalk
floorDistinctPowersOf: b "Answers an array which holds all the numbers b^i + b^j < n, i>j>=0, where n is the receiver. b > 1 (b = 2, for this sequence). Usage: n floorDistinctPowersOf: 2 Answer: #(3 5 6 9 10 12 ...) [all terms < n]" | a n p q terms | terms := OrderedCollection new. n := self. p := b. q := 1. a := p + q. [a < n] whileTrue: [[q < p and: [a < n]] whileTrue: [terms add: a. q := b * q. a := p + q]. p := b * p. q := 1. a := p + q]. ^terms as Array [by Hieronymus Fischer, Apr 20 2014] ------------ -
Smalltalk
invertedDistinctPowersOf: b "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). Usage: m invertedDistinctPowersOf: 2 Answer: n such that a(n) = m, or, if no such n exists, min (k | a(k) >= m)" | n i j k m | m := self. i := m integerFloorLog: b. j := m - (b raisedToInteger: i) integerFloorLog: b. n := i * (i - 1) / 2 + 1 + j. ^n [by Hieronymus Fischer, Apr 20 2014]
Formula
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
a(n) = A059268(n-1) + A140513(n-1). A000120(a(n)) = 2. Complement of A161989. A151774(a(n)) = 1. - Reinhard Zumkeller, Jun 24 2009
A073267(a(n)) = 2. - Reinhard Zumkeller, Mar 07 2012
Start with A000051. If n is in sequence, then so is 2n. - Ralf Stephan, Aug 16 2013
a(n) = A057168(a(n-1)) for n>1 and a(1) = 3. - Marc LeBrun, Jan 01 2014
From Hieronymus Fischer, Apr 20 2014: (Start)
Formulas for a general parameter b according to a(n) = b^i + b^j, i>j>=0; b = 2 for this sequence.
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)].
a(A000217(n)) = (b + 1)*b^(n-1) = b^n + b^(n-1).
a(A000217(n)+1) = 1 + b^(n+1).
a(n + 1 + floor((sqrt(8n - 1) + 1)/2)) = b*a(n).
a(n + 1 + floor(log_b(a(n)))) = b*a(n).
a(n + 1) = b^2/(b+1) * a(n) + 1, if n is a triangular number (s. A000217).
a(n + 1) = b*a(n) + (1-b)* b^floor((sqrt(8n - 1) + 1)/2), if n is not a triangular number.
The next term can also be calculated without using the index n. Let m be a term and i = floor(log_b(m)), then:
a(n + 1) = b*m + (1-b)* b^i, if floor(log_b(m/(b+1))) + 1 < i,
a(n + 1) = b^2/(b+1) * m + 1, if floor(log_b(m/(b+1))) + 1 = i.
Partial sum:
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(8*n - 1) + 1)/2), j = n - 1 - i*(i - 1)/2.
Inverse:
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].
Inequalities:
a(n) <= (b+1)/b * b^floor(sqrt(2n)+1/2), equality holds for triangular numbers.
a(n) > b^floor(sqrt(2n)+1/2).
a(n) < b^sqrt(2n)*sqrt(b).
a(n) > b^sqrt(2n)/sqrt(b).
Asymptotic behavior:
lim sup a(n)/b^sqrt(2n) = sqrt(b).
lim inf a(n)/b^sqrt(2n) = 1/sqrt(b).
lim sup a(n)/b^(floor(sqrt(2n))) = b.
lim inf a(n)/b^(floor(sqrt(2n))) = 1.
lim sup a(n)/b^(floor(sqrt(2n)+1/2)) = (b+1)/b.
lim inf a(n)/b^(floor(sqrt(2n)+1/2)) = 1.
(End)
Sum_{n>=1} 1/a(n) = A179951. - Amiram Eldar, Oct 06 2020
Extensions
Edited by M. F. Hasler, Dec 23 2016
Comments