|
%I #140 Feb 01 2022 18:14:34
%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 Sums of two distinct powers of 2.
%C Appears to give all k such that 8 is the highest power of 2 dividing A005148(k). - _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 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 A073267(a(n)) = 2. - _Reinhard Zumkeller_, Mar 07 2012
%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)
%p a:= n-> (i-> 2^i+2^(n-1-i*(i-1)/2))(floor((sqrt(8*n-1)+1)/2)):
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Feb 01 2022
%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. A000120, 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
| 