A151774 -id:A151774 - cp's OEIS frontend

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

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

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
All odd terms are A000051. - Robert G. Wilson v, Jan 03 2014
A239708 holds the subsequence of terms m such that m - 1 is prime. - Hieronymus Fischer, Apr 20 2014

			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)

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

Cf. A000120, A001969, A048639, A048645, A057168.
Cf. A000217, A179951, A187813, A239708.
Cf. A000079, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (Hamming weight = 1, 3, 4, ..., 9).
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

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

a018900 n = a018900_list !! (n-1)
a018900_list = elemIndices 2 a073267_list  -- Reinhard Zumkeller, Mar 07 2012

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

Select[ Range[ 1056 ], (Count[ IntegerDigits[ #, 2 ], 1 ]==2)& ]
Union[Total/@Subsets[2^Range[0,10],{2}]] (* Harvey P. Dale, Mar 04 2012 *)

for(m=1,9,for(n=0,m-1,print1(2^m+2^n", "))) \\ Charles R Greathouse IV, Sep 09 2011

is(n)=hammingweight(n)==2 \\ Charles R Greathouse IV, Mar 03 2014

for(n=0,10^5,if(hammingweight(n)==2,print1(n,", "))); \\ Joerg Arndt, Mar 04 2014

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

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

A018900_list = [2**a+2**b for a in range(1,10) for b in range(a)] # Chai Wah Wu, Jan 24 2021

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

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]
------------

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]
------------

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]
------------

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]

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

Edited by M. F. Hasler, Dec 23 2016

A340068 a(n) is the number of integers in the set {n+1,n+2, . . . ,2n} whose representation in base 2 contain exactly three digits 1’s.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 6, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 17, 17, 18, 18, 18, 18, 19

Offset: 1

Bernard Schott, Dec 28 2020

This sequence is inspired by the 3rd problem, proposed by Romania, during the 35th International Mathematical Olympiad in 1994 at Hong Kong (see the link IMO).
This sequence is increasing because there are only these two possibilities:
-> a(n+1) - a(n) = 1 if n has exactly two 1's in its binary representation (A018900);
-> a(n+1) - a(n) = 0 otherwise.
Consequence, for any positive integer m, a(x) = m has at least one solution (answer to the 1st Olympiad question).
Only when m = k*(k-1)/2 + 1 with k >= 2 (A000124 \ {1}), there exists only one n such that a(n) = m, and then n = 2^k+2 where k >= 2 (A052548 \ {3, 4}) (answer to the 2nd Olympiad question).

			a(2) = 0 because in {3, 4}, 3 = 11_2 and 4 = 100_2.
a(4) = 1 because in {5, 6, 7, 8, 9, 10} only 7 = 111_2 has 3 digits in its binary representation.
a(6) = 2 because in {7, 8, 9, 10, 11, 12}, there are 7 = 111_2 and 11 = 1011_2 that have 3 digits in their binary representation.

Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 10 and 92-93.

The IMO Compendium, Problem 3, 35th IMO 1994.
Index to sequences related to Olympiads.

Cf. A000120, A014311, A018900, A057168, A151774 (first differences).

a[n_] := Count[Range[n + 1, 2*n], ?(DigitCount[#, 2, 1] == 3 &)]; Array[a, 100] (* _Amiram Eldar, Dec 28 2020 *)

a(n) = sum(k=n+1, 2*n, hammingweight(k) == 3); \\ Michel Marcus, Dec 28 2020

first(n) = {my(res = vector(n), t = 0); for(i = 1, n, res[i] = t; if(hammingweight(i) == 2, t++)); res} \\ David A. Corneth, Dec 29 2020

def a(n): return sum(bin(k)[2:].count("1")==3 for k in range(n+1, 2*n+1))
print([a(n) for n in range(1, 68)]) # Michael S. Branicky, Dec 28 2020

def A340068(n): return sum(1 for k in range(n) if k.bit_count()==2) # Chai Wah Wu, Mar 11 2025

a(2^k+2) = k*(k-1)/2 + 1 for k >= 2.

More terms from David A. Corneth, Dec 28 2020

cp's OEIS Frontend

A018900 Sums of two distinct powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Python

Smalltalk

Smalltalk

Smalltalk

Smalltalk

Formula

Extensions

A151758 G.f.: Theta^2-Theta, where Theta = Sum_{k>=0} x^(2^k).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A161989 Numbers having more than 2 or fewer than 2 ones in their binary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

A340068 a(n) is the number of integers in the set {n+1,n+2, . . . ,2n} whose representation in base 2 contain exactly three digits 1’s.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Python

Formula

Extensions