Project Euler 250: Find the number of non-empty subsets the sum of whose elements is divisible by 250.

---

Problem Description

Find the number of non-empty subsets of {1¹, 2², 3³,…, 250250²⁵⁰²⁵⁰}, the sum of whose elements is divisible by 250. Enter the rightmost 16 digits as your answer.

Analysis

What I thought was a novel and unique DP solution turned out to be one of the most popular ways to solve this problem. It’s solution is very similar to problems 31 and 76.

Setting up the frequency array of modulus powers was an early observation. It has an interesting pattern that could be used to further optimize the program, but adding the code to do so may obscure the simple premise used below.

See the frequency table is in the comments section.

Also, you have to subtract one from the final result to exclude the empty set. It sums to 0 and is divisible by 250. Not accounting for this will cause much confusion, frustration and anger.

Project Euler 250 Solution

Runs < 12 seconds in Python 2.7.

Use this link to get the Project Euler 250 Solution Python 2.7 source.

Afterthoughts

• A neat optimization I learned from the forums was to change:
  


freq, t, tx = [0]*m, [0]*m, [0]*m
. . .
for k in range(m):
  tx[k] = (t[k] + t[(k-i)]) % 10**16
t, tx = tx, t

to:

freq, t = [0]*m, [0]*m
. . .
  t = [(t[k] + t[(k-i)]) % 10**16 for k in range(m)]

It is faster and saves having an extra temporary array.

Frequency (freq) array:
[25025, 1001, 0, 1001, 1001, 0, 3003, 1002, 0, 1001, 0, 1001, 0, 1001, 1000, 0, 3002, 1002, 0, 1001, 0,
1001, 0, 1001, 1000, 0, 3002, 1001, 0, 1001, 0, 1001, 0, 1000, 1000, 0, 3002, 1001, 0, 1001, 0, 1001,
0, 1001, 1000, 0, 3003, 1002, 0, 1001, 0, 1001, 0, 1002, 1002, 0, 3003, 1001, 0, 1001, 0, 1001, 0,
1001, 1001, 0, 3004, 1001, 0, 1001, 0, 1001, 0, 1000, 1001, 0, 3003, 1001, 0, 1001, 0, 1001, 0, 1001,
1001, 0, 3004, 1001, 0, 1001, 0, 1001, 0, 1001, 1001, 0, 3003, 1001, 0, 1001, 0, 1001, 0, 1002, 1001,
0, 3003, 1000, 0, 1001, 0, 1001, 0, 1002, 1002, 0, 3002, 1000, 0, 1001, 0, 1001, 0, 1001, 1001, 25025,
3003, 1001, 0, 1001, 0, 1001, 0, 1002, 1002, 0, 3002, 1000, 0, 1001, 0, 1001, 0, 1002, 1001, 0, 3003,
1000, 0, 1001, 0, 1001, 0, 1001, 1001, 0, 3003, 1001, 0, 1001, 0, 1001, 0, 1001, 1000, 0, 3003, 1001,
0, 1001, 0, 1001, 0, 1001, 1001, 0, 3003, 1002, 0, 1001, 0, 1001, 0, 1001, 1000, 0, 3003, 1001, 0,
1001, 0, 1001, 0, 1001, 1001, 0, 3002, 1000, 0, 1001, 0, 1001, 0, 1000, 1001, 0, 3004, 1001, 0, 1001,
0, 1001, 0, 1001, 1002, 0, 3004, 1002, 0, 1001, 0, 1001, 0, 1001, 1002, 0, 3004, 1001, 0, 1001, 0,
1001, 0, 1000, 1002, 0, 3004, 1001, 0, 1001, 0, 1001, 0, 1000, 1001, 0, 3003, 1001, 0, 1001]

Full Answer:
1913632767165333770252234310750163069834160429303722710242211912885821718320699719386481255946529840771
3258880554002523809000550181004722164691990791796216105528723914179082619897309829010183163626973355855
5999306330315600310099410619568592185583809345129002163399193048347346020632534085343254677339405056184
7326428202599457670106733005406613103334980070826842988423932453124198773054240892462448194753422597637
6555562298413900685441068866107561528290456061485273224655196316704209155036705345243851360338784496710
2702168073260334966060683376208542265749847926446026321759054761268936741149541380503413974000836131117
3214555396194146231774532331102407509287029942492977551763290783785267079641982184476608545105167745590
2390241353210723566485746027488888458569654959430268044630917086876645201216270720136185137433124560024
4947237368359497976815295054111032824969593334891995366826402669957540356158979566968433103910065837234
7600252380629942243992227333522004241293221027559893329018350365802362213819847196012583447620759990629
0500807343271503733998277415625719154124582562365219998050976471531150922171863821067274781684862358971
6877531079379698868451514069003423205128173741148232662970193131629240486253267005757414501962383708763
4789370282599541846772457881907410198573338156795014690730557060377219108717480651566762078196494232718
4441019702657518888262582004442297863308082520897408190969125434496636680390937830047369772525876500386
6695072692075426517044629260507081158000321869747531690336924001456388953753220118461473200202913003821
3308573405644391091766581424660875716741854196533005965673813314809931088245808990069485886556688851346
4366843244471303419027893034670915768823776259993094129652301345812142548060209xxxx

replace the last four x’s with the last four digits of your answer.