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

%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