← Complete problem index

PROJECT EULER · #0937

Equiproduct Partition

Statement only · UnsolvedOriginal problem ↗

Let θ=−2.

Define T to be the set of numbers of the form a+bθ, where a and b are integers and either a>0, or a=0 and b>0. For a set S⊆T and element z∈T, define p(S,z) to be the number of ways of choosing two distinct elements from S with product either z or −z.

For example if S={1,2,4} and z=4, there is only one valid pair of elements with product ±4, namely 1 and 4. Thus, in this case p(S,z)=1.

For another example, if S={1,θ,1+θ,2−θ} and z=2−θ, we have 1⋅(2−θ)=z and θ⋅(1+θ)=−z, giving p(S,z)=2.

Let A and B be two sets satisfying the following conditions:

  • 1∈A
  • A∩B=∅
  • A∪B=T
  • p(A,z)=p(B,z) for all z∈T

Remarkably, these four conditions uniquely determine the sets A and B.

Let Fn be the set of the first n factorials: Fn={1!,2!,…,n!}, and define G(n) to be the sum of all elements of Fn∩A.

You are given G(4)=25, G(7)=745, and G(100)≡709772949(mod109+7).

Find G(108) and give your answer modulo 109+7.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.