A343943 Number of distinct possible alternating sums of permutations of the multiset of prime factors of n.

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, 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, 2, 3, 1, 3, 1, 2, 2, 2, 2, 3, 1, 2, 1, 2, 1, 4, 2, 2, 2

Offset: 1

Author

Gus Wiseman, Aug 19 2021

Keywords

• nonn

Comments

First differs from A096825 at a(525) = 3, A096825(525) = 4.

First differs from A345926 at a(90) = 4, A345926(90) = 3.

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 factors is also the reverse-alternating sum of reversed prime factors.

Also the number of distinct "sums of prime factors" of divisors d|n such that bigomega(d) = bigomega(n)/2 rounded up.

Examples

			The divisors of 525 with 2 prime factors are: 15, 21, 25, 35, with prime factors {3,5}, {3,7}, {5,5}, {5,7}, with distinct sums {8,10,12}, so a(525) = 3.
		

Crossrefs

The half-length submultisets are counted by A114921.

Including all multisets of prime factors gives A305611(n) + 1.

The strict rounded version appears to be counted by A342343.

The version for prime indices instead of prime factors is A345926.

A000005 counts divisors, which add up to A000203.

A001414 adds up prime factors, row sums of A027746.

A056239 adds up prime indices, row sums of A112798.

A071321 gives the alternating sum of prime factors (reverse: A071322).

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

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

A108917 counts knapsack partitions, ranked by A299702.

A276024 and A299701 count positive subset-sums of partitions.

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

A334968 counts subsequence-sums of standard compositions.

Cf. A008549, A032443, A083399, A096825, A344609, A345957.

Programs

Mathematica

prifac[n_]:=If[n==1,{},Flatten[ConstantArray@@@FactorInteger[n]]];
Table[Length[Union[Total/@Subsets[prifac[n],{Ceiling[PrimeOmega[n]/2]}]]],{n,100}]

Python

from sympy import factorint
from sympy.utilities.iterables import multiset_combinations
def A343943(n):
    fs = factorint(n)
    return len(set(sum(d) for d in multiset_combinations(fs,(sum(fs.values())+1)//2))) # Chai Wah Wu, Aug 23 2021