|
|
A018900
|
|
Sums of two distinct powers of 2.
|
|
73
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Appears to give all k such that 8 is the highest power of 2 dividing A005148(k). - Benoit Cloitre, Jun 22 2002
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
Numbers whose base-2 sum of digits is 2. - Tom Edgar, Aug 31 2013
|
|
LINKS
|
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.
|
|
FORMULA
|
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(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(8n - 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)
|
|
EXAMPLE
|
a(1) = 3, since 2 = 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)
|
|
MAPLE
|
a:= n-> (i-> 2^i+2^(n-1-i*(i-1)/2))(floor((sqrt(8*n-1)+1)/2)):
|
|
MATHEMATICA
|
Select[ Range[ 1056 ], (Count[ IntegerDigits[ #, 2 ], 1 ]==2)& ]
Union[Total/@Subsets[2^Range[0, 10], {2}]] (* Harvey P. Dale, Mar 04 2012 *)
|
|
PROG
|
(PARI) for(n=0, 10^5, if(hammingweight(n)==2, print1(n, ", "))); \\ Joerg Arndt, Mar 04 2014
(Haskell)
a018900 n = a018900_list !! (n-1)
(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;
}
if (n == 1) return 3;
(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)
------------
(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
------------
(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
------------
(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
(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
|
|
CROSSREFS
|
Cf. A000079, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (Hamming weight = 1, 3, 4, ..., 9).
|
|
KEYWORD
|
|
|
AUTHOR
|
Jonn Dalton (jdalton(AT)vnet.ibm.com), Dec 11 1996
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|