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
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, 512, 7, 1024, 5, 18, 65, 12, 6, 2048, 129, 34, 7, 4096, 11, 8192, 18, 8, 257, 16384, 6, 16, 9, 66, 34, 32768, 7, 20, 11, 130, 513, 65536, 8, 131072, 1025, 12, 6, 36, 19 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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.

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

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.

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..1024

FORMULA

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

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]

From Antti Karttunen, Jul 29 2015: (Start)

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

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

Other identities. For all n >= 0:

a(A019565(n)) = n.

a(A260443(n)) = n.

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

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

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

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

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

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

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

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

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

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

(End)

a(1) = 0, a(2n) = 1+a(n), a(2n+1) = 2*a(A064989(2n+1)). - Antti Karttunen, Oct 11 2016

MAPLE

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.

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;

# simpler alternative

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

map(f, [$1..100]); # Robert Israel, Oct 10 2016

MATHEMATICA

a[1] = 0; a[n_] := Total[ #[[2]]*2^(PrimePi[#[[1]]]-1)& /@ FactorInteger[n] ]; Array[a, 100] (* Jean-Fran├žois Alcover, Mar 15 2016 *)

PROG

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

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

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

;; Antti Karttunen, Jul 29 2015

(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

(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

(Python)

from sympy import factorint, primepi

def a(n):

    if n==1: return 0

    f=factorint(n)

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

print [a(n) for n in xrange(1, 101)] # Indranil Ghosh, Jun 19 2017

CROSSREFS

Row 2 of A104244.

Left inverse of both A019565 and A260443.

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

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

Sequence in context: A324756 A324754 A174220 * A162474 A285330 A048676

Adjacent sequences:  A048672 A048673 A048674 * A048676 A048677 A048678

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jul 14 1999

EXTENSIONS

Entry revised by Antti Karttunen, Jul 29 2015

More linking formulas added by Antti Karttunen, Apr 18 2017

STATUS

approved

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 May 23 20:23 EDT 2019. Contains 323528 sequences. (Running on oeis4.)