cp's OEIS Frontend

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

%I A048675 #131 Jul 21 2025 23:03:13
%S A048675 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 A048675 512,7,1024,5,18,65,12,6,2048,129,34,7,4096,11,8192,18,8,257,16384,6,
%U A048675 16,9,66,34,32768,7,20,11,130,513,65536,8,131072,1025,12,6,36,19
%N 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).
%C A048675 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 A048675 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 A048675 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 A048675 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
%C A048675 If the binary rank of an integer partition y is given by Sum_i 2^(y_i-1), and the Heinz number is Product_i prime(y_i), then a(n) is the binary rank of the integer partition with Heinz number n. Note the function taking a set s to Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices), and the function taking a multiset m to Product_i prime(m_i) is the inverse of A112798 (prime indices). - _Gus Wiseman_, May 22 2024
%H A048675 Antti Karttunen, <a href="/A048675/b048675.txt">Table of n, a(n) for n = 1..1024</a>
%H A048675 Hans Havermann, <a href="/A048675/a048675.txt">Factorization of the first 10000 terms, in format [[primes], [exponents]]</a>
%F A048675 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 A048675 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 A048675 From _Antti Karttunen_, Jul 29 2015: (Start)
%F A048675 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 A048675 a(1) = 0; for n > 1, a(n) = (A067029(n) * (2^(A055396(n)-1))) + a(A028234(n)).
%F A048675 Other identities. For all n >= 0:
%F A048675 a(A019565(n)) = n.
%F A048675 a(A260443(n)) = n.
%F A048675 a(A206296(n)) = A000129(n).
%F A048675 a(A005940(n+1)) = A087808(n).
%F A048675 a(A007913(n)) = A248663(n).
%F A048675 a(A007947(n)) = A087207(n).
%F A048675 a(A283477(n)) = A005187(n).
%F A048675 a(A284003(n)) = A006068(n).
%F A048675 a(A285101(n)) = A028362(1+n).
%F A048675 a(A285102(n)) = A068052(n).
%F A048675 Also, it seems that a(A163511(n)) = A135529(n) for n >= 1. (End)
%F A048675 a(1) = 0, a(2n) = 1+a(n), a(2n+1) = 2*a(A064989(2n+1)). - _Antti Karttunen_, Oct 11 2016
%F A048675 From _Peter Munn_, Jan 31 2020: (Start)
%F A048675 a(n^2) = a(A003961(n)) = 2 * a(n).
%F A048675 a(A297845(n,k)) = a(n) * a(k).
%F A048675 a(n) = a(A225546(n)).
%F A048675 a(A329332(n,k)) = n * k.
%F A048675 a(A329050(n,k)) = 2^(n+k).
%F A048675 (End)
%F A048675 From _Antti Karttunen_, Feb 02-25 2020, Feb 01 2021: (Start)
%F A048675 a(n) = Sum_{d|n} A297108(d) = Sum_{d|A225546(n)} A297108(d).
%F A048675 a(n) = a(A097248(n)).
%F A048675 For n >= 2:
%F A048675 A001221(a(n)) = A322812(n), A001222(a(n)) = A277892(n).
%F A048675 A000203(a(n)) = A324573(n), A033879(a(n)) = A324575(n).
%F A048675 For n >= 1, A331750(n) = a(A000203(n)).
%F A048675 For n >= 1, the following chains hold:
%F A048675 A293447(n) >= a(n) >= A331740(n) >= A331591(n).
%F A048675 a(n) >= A087207(n) >= A248663(n).
%F A048675 (End)
%F A048675 a(n) = A087207(A097248(n)). - _Flávio V. Fernandes_, Jul 16 2025
%e A048675 From _Gus Wiseman_, May 22 2024: (Start)
%e A048675 The A018819(7) = 6 cases of binary rank 7 are the following, together with their prime indices:
%e A048675    30: {1,2,3}
%e A048675    40: {1,1,1,3}
%e A048675    54: {1,2,2,2}
%e A048675    72: {1,1,1,2,2}
%e A048675    96: {1,1,1,1,1,2}
%e A048675   128: {1,1,1,1,1,1,1}
%e A048675 (End)
%p A048675 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 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 A048675 # simpler alternative
%p A048675 f:= n -> add(2^(numtheory:-pi(t[1])-1)*t[2], t=ifactors(n)[2]):
%p A048675 map(f, [$1..100]); # _Robert Israel_, Oct 10 2016
%t A048675 a[1] = 0; a[n_] := Total[ #[[2]]*2^(PrimePi[#[[1]]]-1)& /@ FactorInteger[n] ]; Array[a, 100] (* _Jean-François Alcover_, Mar 15 2016 *)
%o A048675 (Scheme, with memoization-macro definec, two alternatives)
%o A048675 (definec (A048675 n) (cond ((= 1 n) (- n 1)) (else (+ (A000079 (- (A055396 n) 1)) (A048675 (A032742 n))))))
%o A048675 (definec (A048675 n) (cond ((= 1 n) (- n 1)) (else (+ (* (A067029 n) (A000079 (- (A055396 n) 1))) (A048675 (A028234 n))))))
%o A048675 ;; _Antti Karttunen_, Jul 29 2015
%o A048675 (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 A048675 (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 A048675 (PARI)
%o A048675 \\ The following program reconstructs terms (e.g. for checking purposes) from the factorization file prepared by Hans Havermann:
%o A048675 v048675sigs = readvec("a048675.txt");
%o A048675 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 A048675 (Python)
%o A048675 from sympy import factorint, primepi
%o A048675 def a(n):
%o A048675     if n==1: return 0
%o A048675     f=factorint(n)
%o A048675     return sum([f[i]*2**(primepi(i) - 1) for i in f])
%o A048675 print([a(n) for n in range(1, 51)]) # _Indranil Ghosh_, Jun 19 2017
%Y A048675 Row 2 of A104244.
%Y A048675 Similar logarithmic functions: A001414, A056239, A090880, A289506, A293447.
%Y A048675 Left inverse of the following sequences: A000079, A019565, A038754, A068911, A134683, A260443, A332824.
%Y A048675 A003961, A028234, A032742, A055396, A064989, A067029, A225546, A297845 are used to express relationship between terms of this sequence.
%Y A048675 Cf. also A048623, A048676, A099884, A277896 and tables A277905, A285325.
%Y A048675 Cf. A297108 (Möbius transform), A332813 and A332823 [= a(n) mod 3].
%Y A048675 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), (A248692,A056239), (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 A048675 See comments/formulas in A277333, A331591, A331740 giving their relationship to this sequence.
%Y A048675 The formula section details how the sequence maps the terms of A329050, A329332.
%Y A048675 A277892, A322812, A322869, A324573, A324575 give properties of the n-th term of this sequence.
%Y A048675 The term k appears A018819(k) times.
%Y A048675 The inverse transformation is A019565 (Heinz number of binary indices).
%Y A048675 The version for distinct prime indices is A087207.
%Y A048675 Numbers k such that a(k) is prime are A277319, counts A372688.
%Y A048675 Grouping by image gives A277905.
%Y A048675 A014499 lists binary indices of prime numbers.
%Y A048675 A061395 gives greatest prime index, least A055396.
%Y A048675 A112798 lists prime indices, length A001222, reverse A296150, sum A056239.
%Y A048675 Binary indices:
%Y A048675 - listed A048793, sum A029931
%Y A048675 - reversed A272020
%Y A048675 - opposite A371572, sum A230877
%Y A048675 - length A000120, complement A023416
%Y A048675 - min A001511, opposite A000012
%Y A048675 - max A070939, opposite A070940
%Y A048675 - complement A368494, sum A359400
%Y A048675 - opposite complement A371571, sum A359359
%Y A048675 Cf. A000720, A035100, A071814, A096111, A225620, A243055, A304818, A355536, A358136, A372890.
%Y A048675 Cf. A087207, A097248.
%K A048675 nonn
%O A048675 1,3
%A A048675 _Antti Karttunen_, Jul 14 1999
%E A048675 Entry revised by _Antti Karttunen_, Jul 29 2015
%E A048675 More linking formulas added by _Antti Karttunen_, Apr 18 2017