login
This site is supported by donations to The OEIS Foundation.

 

Logo


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). 121

%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.

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

%F A001222(a(n)) = A277892(n) for n >= 2.

%F (End)

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

%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 (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 xrange(1, 101)] # _Indranil Ghosh_, Jun 19 2017

%Y Row 2 of A104244.

%Y Left inverse of both A019565 and A260443.

%Y Cf. A000079, A028234, A032742, A055396, A067029.

%Y Cf. also A048623, A048676, A064989, A099884, A206296, A277333, A277892, A277896 and tables A277905, A285325.

%K nonn

%O 1,3

%A _Antti Karttunen_, Jul 14 1999

%E Entry revised by _Antti Karttunen_, Jul 29 2015

%E More linking formulas added by _Antti Karttunen_, Apr 18 2017

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 15 17:43 EDT 2019. Contains 324142 sequences. (Running on oeis4.)