The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k). 140

%I

%S 0,1,2,2,4,3,8,3,4,5,16,4,32,9,6,4,64,5,128,6,10,17,256,5,8,33,6,10,

%T 512,7,1024,5,18,65,12,6,2048,129,34,7,4096,11,8192,18,8,257,16384,6,

%U 16,9,66,34,32768,7,20,11,130,513,65536,8,131072,1025,12,6,36,19

%N If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).

%C The original motivation for this sequence was to encode the prime factorization of n in the binary representation of a(n), each such representation being unique as long as this map is restricted to A005117 (squarefree numbers, resulting a permutation of nonnegative integers A048672) or any of its subsequence, resulting an injective function like A048623 and A048639.

%C However, also the restriction to A260443 (not all terms of which are squarefree) results a permutation of nonnegative integers, namely A001477, the identity permutation.

%C When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443), then a(n) gives the evaluation of that polynomial at x=2.

%C The primitive completely additive integer sequence that satisfies a(n) = a(A225546(n)), n >= 1. By primitive, we mean that if b is another such sequence, then there is an integer k such that b(n) = k * a(n) for all n >= 1. - _Peter Munn_, Feb 03 2020

%H Antti Karttunen, <a href="/A048675/b048675.txt">Table of n, a(n) for n = 1..1024</a>

%H Hans Havermann, <a href="/A048675/a048675.txt">Factorization of the first 10000 terms, in format [[primes], [exponents]]</a>

%F a(1) = 0, a(n) = 1/2 * (e1*2^i1 + e2*2^i2 + ... + ez*2^iz) if n = p_{i1}^e1*p_{i2}^e2*...*p_{iz}^ez, where p_i is the i-th prime. (e.g. p_1 = 2, p_2 = 3).

%F Totally additive with a(p^e) = e * 2^(PrimePi(p)-1), where PrimePi(n) = A000720(n). [Missing factor e added to the comment by _Antti Karttunen_, Jul 29 2015]

%F From _Antti Karttunen_, Jul 29 2015: (Start)

%F a(1) = 0; for n > 1, a(n) = 2^(A055396(n)-1) + a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n.]

%F a(1) = 0; for n > 1, a(n) = (A067029(n) * (2^(A055396(n)-1))) + a(A028234(n)).

%F Other identities. For all n >= 0:

%F a(A019565(n)) = n.

%F a(A260443(n)) = n.

%F a(A206296(n)) = A000129(n).

%F a(A005940(n+1)) = A087808(n).

%F a(A007913(n)) = A248663(n).

%F a(A007947(n)) = A087207(n).

%F a(A283477(n)) = A005187(n).

%F a(A284003(n)) = A006068(n).

%F a(A285101(n)) = A028362(1+n).

%F a(A285102(n)) = A068052(n).

%F Also, it seems that a(A163511(n)) = A135529(n) for n >= 1. (End)

%F a(1) = 0, a(2n) = 1+a(n), a(2n+1) = 2*a(A064989(2n+1)). - _Antti Karttunen_, Oct 11 2016

%F From _Peter Munn_, Jan 31 2020: (Start)

%F a(n^2) = a(A003961(n)) = 2 * a(n).

%F a(A297845(n,k)) = a(n) * a(k).

%F a(n) = a(A225546((n)).

%F a(A329332(n,k)) = n * k.

%F a(A329050(n,k)) = 2^(n+k).

%F (End)

%F From _Antti Karttunen_, Feb 02-25 2020: (Start)

%F a(n) = Sum_{d|n} A297108(d).

%F a(n) = a(A097248(n)).

%F For n >= 2:

%F A001221(a(n)) = A322812(n), A001222(a(n)) = A277892(n).

%F A000203(a(n)) = A324573(n), A033879(a(n)) = A324575(n).

%F For n >= 1, A331750(n) = a(A000203(n)).

%F For n >= 1, the following chains hold:

%F A293447(n) >= a(n) >= A331740(n) >= A331591(n).

%F a(n) >= A087207(n) >= A248663(n).

%F (End)

%p nthprime := proc(n) local i; if(isprime(n)) then for i from 1 to 1000000 do if(ithprime(i) = n) then RETURN(i); fi; od; else RETURN(0); fi; end; # nthprime(2) = 1, nthprime(3) = 2, nthprime(5) = 3, etc. - this is also A049084.

%p A048675 := proc(n) local s,d; s := 0; for d in ifactors(n)[ 2 ] do s := s + d[ 2 ]*(2^(nthprime(d[ 1 ])-1)); od; RETURN(s); end;

%p # simpler alternative

%p f:= n -> add(2^(numtheory:-pi(t[1])-1)*t[2], t=ifactors(n)[2]):

%p map(f, [\$1..100]); # _Robert Israel_, Oct 10 2016

%t a[1] = 0; a[n_] := Total[ #[[2]]*2^(PrimePi[#[[1]]]-1)& /@ FactorInteger[n] ]; Array[a, 100] (* _Jean-François Alcover_, Mar 15 2016 *)

%o (Scheme, with memoization-macro definec, two alternatives)

%o (definec (A048675 n) (cond ((= 1 n) (- n 1)) (else (+ (A000079 (- (A055396 n) 1)) (A048675 (A032742 n))))))

%o (definec (A048675 n) (cond ((= 1 n) (- n 1)) (else (+ (* (A067029 n) (A000079 (- (A055396 n) 1))) (A048675 (A028234 n))))))

%o ;; _Antti Karttunen_, Jul 29 2015

%o (definec (A048675 n) (cond ((= 1 n) 0) ((even? n) (+ 1 (A048675 (/ n 2)))) (else (* 2 (A048675 (A064989 n)))))) ;; Third one, using the new recurrence. - _Antti Karttunen_, Oct 11 2016

%o (PARI) a(n) = my(f = factor(n)); sum(k=1, #f~, f[k,2]*2^primepi(f[k,1]))/2; \\ _Michel Marcus_, Oct 10 2016

%o (PARI)

%o \\ The following program reconstructs terms (e.g. for checking purposes) from the factorization file prepared by Hans Havermann:

%o A048675(n) = if(n<=2,n-1,my(prsig=v048675sigs[n],ps=prsig[1],es=prsig[2]); prod(i=1,#ps,ps[i]^es[i])); \\ _Antti Karttunen_, Feb 02 2020

%o (Python)

%o from sympy import factorint, primepi

%o def a(n):

%o if n==1: return 0

%o f=factorint(n)

%o return sum([f[i]*2**(primepi(i) - 1) for i in f])

%o print([a(n) for n in range(1, 51)]) # _Indranil Ghosh_, Jun 19 2017

%Y Row 2 of A104244.

%Y Similar logarithmic functions: A001414, A056239, A090880, A289506, A293447.

%Y Left inverse of the following sequences: A000079, A019565, A038754, A068911, A134683, A260443, A332824.

%Y A003961, A028234, A032742, A055396, A064989, A067029, A225546, A297845 are used to express relationship between terms of this sequence.

%Y Cf. also A048623, A048676, A099884, A277896 and tables A277905, A285325.

%Y Cf. A297108 (Möbius transform), A332813 and A332823 [= a(n) mod 3].

%Y Pairs of sequences (f,g) that satisfy a(f(n)) = g(n), possibly with offset change: (A000203,A331750), (A005940,A087808), (A007913,A248663), (A007947,A087207), (A097248,A048675), (A206296,A000129), (A283477,A005187), (A284003,A006068), (A285101,A028362), (A285102,A068052), (A293214,A001065), (A318834,A051953), (A319991,A293897), (A319992,A293898), (A320017,A318674), (A329352,A069359), (A332461,A156552), (A332462,A156552), (A332825,A000010) and apparently (A163511,A135529).

%Y See comments/formulas in A277333, A331591, A331740 giving their relationship to this sequence.

%Y The formula section details how the sequence maps the terms of A329050, A329332.

%Y A277892, A322812, A322869, A324573, A324575 give properties of the n-th term of this sequence.

%K nonn,changed

%O 1,3

%A _Antti Karttunen_, Jul 14 1999

%E Entry revised by _Antti Karttunen_, Jul 29 2015