login
Number of distinct possible alternating sums of permutations of the multiset of prime indices of n.
6

%I #17 Aug 23 2021 13:39:00

%S 1,1,1,1,1,2,1,1,1,2,1,2,1,2,2,1,1,2,1,2,2,2,1,2,1,2,1,2,1,3,1,1,2,2,

%T 2,3,1,2,2,2,1,3,1,2,2,2,1,2,1,2,2,2,1,2,2,2,2,2,1,4,1,2,2,1,2,3,1,2,

%U 2,3,1,3,1,2,2,2,2,3,1,2,1,2,1,4,2,2,2,2,1,3,2,2,2,2,2,2,1,2,2,3

%N Number of distinct possible alternating sums of permutations of the multiset of prime indices of n.

%C First differs from A096825 at a(90) = 3, A096825(90) = 4.

%C A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

%C The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i. Of course, the alternating sum of prime indices is also the reverse-alternating sum of reversed prime indices.

%C Also the number of possible values of A056239(d) where d is a divisor of n with half as many prime factors (rounded up) as n.

%e Grouping the 12 permutations of {1,2,2,3} by alternating sum k gives:

%e k = -2: (1223) (1322) (2213) (2312)

%e k = 0: (1232) (2123) (2321) (3212)

%e k = 2: (2132) (2231) (3122) (3221)

%e so a(90) = 3.

%t primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];

%t Table[Length[Union[ats/@Permutations[primeMS[n]]]],{n,100}]

%o (Python)

%o from sympy import factorint, primepi

%o from sympy.utilities.iterables import multiset_combinations

%o def A345926(n):

%o fs = dict((primepi(a),b) for (a,b) in factorint(n).items())

%o return len(set(sum(d) for d in multiset_combinations(fs, (sum(fs.values())+1)//2))) # _Chai Wah Wu_, Aug 23 2021

%Y The version for prime factors instead of indices is A343943.

%Y A000005 counts divisors.

%Y A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.

%Y A001414 adds up prime factors, row sums of A027746.

%Y A056239 adds up prime indices, row sums of A112798.

%Y A097805 counts compositions by alternating (or reverse-alternating) sum.

%Y A103919 counts partitions by sum and alternating sum (reverse: A344612).

%Y A316524 gives the alternating sum of prime indices (reverse: A344616).

%Y A345197 counts compositions by length and alternating sum.

%Y A344610 counts partitions by sum and positive reverse-alternating sum.

%Y Cf. A008549, A032443, A083399, A096825, A239830, A344607, A344609, A344651, A345957, A345960, A345961.

%K nonn

%O 1,6

%A _Gus Wiseman_, Jul 14 2021