A089625 Replace 2^k in binary expansion of n with (k+1)-st prime.

2, 3, 5, 5, 7, 8, 10, 7, 9, 10, 12, 12, 14, 15, 17, 11, 13, 14, 16, 16, 18, 19, 21, 18, 20, 21, 23, 23, 25, 26, 28, 13, 15, 16, 18, 18, 20, 21, 23, 20, 22, 23, 25, 25, 27, 28, 30, 24, 26, 27, 29, 29, 31, 32, 34, 31, 33, 34, 36, 36, 38, 39, 41, 17, 19, 20, 22, 22, 24, 25, 27

Offset: 1

Author

Reinhard Zumkeller, Dec 31 2003

Keywords

• nonn
• look
• tabf

Examples

			n=25 -> '11001': a(25) = 1*11 + 1*7 + 0*5 + 0*3 + 1*2 = 20.
This sequence regarded as a triangle with rows of lengths  1, 2, 4, 8, 16, ...:
  2
  3, 5
  5, 7, 8, 10
  7, 9, 10, 12, 12, 14, 15, 17
  11, 13, 14, 16, 16, 18, 19, 21, 18, 20, 21, 23, 23, 25, 26, 28
  ... - _Philippe Deléham_, Jun 07 2015
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Binary
• Eric Weisstein's World of Mathematics, Prime Partition.
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A007088, A000586, A000009.

Other sequences that are built by replacing 2^k in the binary representation with other numbers: A029931 (natural numbers), A059590 (factorials), A022290 (Fibonacci).

Cf. A001414, A008472, A019565.

Programs

Haskell

a089625 n = f n 0 a000040_list where
   f 0 y _      = y
   f x y (p:ps) = f x' (y + p * r) ps where (x',r) = divMod x 2
-- Reinhard Zumkeller, Oct 03 2012

Maple

f:= proc(n) local L,j;
  L:= convert(n,base,2);
  add(L[i]*ithprime(i),i=1..nops(L))
end proc:
map(f, [$1..100]); # Robert Israel, Jun 08 2015

Mathematica

a[n_] := With[{bb = IntegerDigits[n, 2]}, bb.Prime[Range[Length[bb], 1, -1]]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Oct 27 2021 *)

PARI

a(n)=my(v=Vecrev(binary(n)),s,i);forprime(p=2,prime(#v),s+=v[i++]*p);s \\ Charles R Greathouse IV, Sep 23 2012

Python

from sympy import nextprime
def A089625(n):
    c, p = 0, 2
    while n:
        if n&1:
            c += p
        n >>=1
        p = nextprime(p)
    return c # Chai Wah Wu, Aug 09 2023

Formula

a(n) = Sum_{i=0..L(n)-1} b(i)*prime(i+1) where L=A070939 and b is defined by n = Sum_{i=0..L(n)-1} b(i)*2^i.

G.f.: 1/(1-x) * Sum_{k>=0} prime(k+1)*x^2^k/(1+x^2^k).

a(A000079(n)) = A000040(n+1).

a(A000225(n)) = A007504(n).

A000586(n) > 0 iff n = a(m) for some m.

a(n) = n for n = 9, 10, or 12.

a(n) = Sum_{k>=0} A030308(n,k)*A000040(k+1). - Philippe Deléham, Oct 15 2011

log n log log n << a(n) << log^2 n log log n. - Charles R Greathouse IV, Sep 23 2012

For n >= 8, a(n) <= m*(m+1)*(log(m)+log(log(m)))/2 where m = ceiling(log_2(n)). - Robert Israel, Jun 08 2015

a(n) = A001414(A019565(n)) = A008472(A019565(n)) for n>=1. - Flávio V. Fernandes, Feb 24 2025