cp's OEIS Frontend

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

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