%I #54 Aug 09 2023 11:47:03
%S 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,
%T 21,23,23,25,26,28,13,15,16,18,18,20,21,23,20,22,23,25,25,27,28,30,24,
%U 26,27,29,29,31,32,34,31,33,34,36,36,38,39,41,17,19,20,22,22,24,25,27
%N Replace 2^k in binary expansion of n with (k+1)-st prime.
%C a(A000079(n)) = A000040(n+1); a(A000225(n)) = A007504(n);
%C A000586(n) > 0 iff n = a(m) for some m;
%C a(n) = n for n = 9, 10, or 12.
%H Reinhard Zumkeller, <a href="/A089625/b089625.txt">Table of n, a(n) for n = 1..10000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Binary.html">Binary</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrimePartition.html">Prime Partition.</a>
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F 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.
%F G.f.: 1/(1-x) * Sum_{k>=0} prime(k+1)*x^2^k/(1+x^2^k).
%F a(n) = Sum_{k>=0} A030308(n,k)*A000040(k+1). - _Philippe Deléham_, Oct 15 2011
%F log n log log n << a(n) << log^2 n log log n. - _Charles R Greathouse IV_, Sep 23 2012
%F 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
%e n=25 -> '11001': a(25) = 1*11 + 1*7 + 0*5 + 0*3 + 1*2 = 20.
%e This sequence regarded as a triangle with rows of lengths 1, 2, 4, 8, 16, ...:
%e 2
%e 3, 5
%e 5, 7, 8, 10
%e 7, 9, 10, 12, 12, 14, 15, 17
%e 11, 13, 14, 16, 16, 18, 19, 21, 18, 20, 21, 23, 23, 25, 26, 28
%e 13, ... - _Philippe Deléham_, Jun 07 2015
%p f:= proc(n) local L,j;
%p L:= convert(n,base,2);
%p add(L[i]*ithprime(i),i=1..nops(L))
%p end proc:
%p map(f, [$1..100]); # _Robert Israel_, Jun 08 2015
%t a[n_] := With[{bb = IntegerDigits[n, 2]}, bb.Prime[Range[Length[bb], 1, -1]]];
%t Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Oct 27 2021 *)
%o (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
%o (Haskell)
%o a089625 n = f n 0 a000040_list where
%o f 0 y _ = y
%o f x y (p:ps) = f x' (y + p * r) ps where (x',r) = divMod x 2
%o -- _Reinhard Zumkeller_, Oct 03 2012
%o (Python)
%o from sympy import nextprime
%o def A089625(n):
%o c, p = 0, 2
%o while n:
%o if n&1:
%o c += p
%o n >>=1
%o p = nextprime(p)
%o return c # _Chai Wah Wu_, Aug 09 2023
%Y Cf. A007088, A000586, A000009.
%Y Other sequences that are built by replacing 2^k in the binary representation with other numbers: A029931 (natural numbers), A059590 (factorials), A022290 (Fibonacci).
%K nonn,tabf
%O 1,1
%A _Reinhard Zumkeller_, Dec 31 2003