Problem 250

[Lord_Farin]

I have been spending a lot of time on this problem the last few days, and I am pretty certain that my approach is correct, and that the code that I use for it is also correct. In spite that, the answer is rejected. Is there someone whom would be willing to take a peek at my (Mathematica) code?

[zwuupeape]

Make sure you did not include the empty set - by convention it sums up to 0 which is divisible by 250

[Lord_Farin]

I have included the empty set in my calculations and considerations, nonetheless the answer is wrong... Also, my algorithm yields the correct answer for any trivial case I can think of and compute by hand. Thus disappointed, I thoroughly reconsidered my algorithm, only to confirm that I completely agree with it, and that it should work.

[Hippunky]

I've gotten (very easy I know!) the count of each of the mod 250 values of x^x for x in 1..250250, e.g. 25025 "x^x"'s result in 0 mod 250, 1001 "x^x"'s result in 1 mod 250 etc.

Any suggestions as to the next step to take? Please be vagueish as I don't want a solution - just an idea of where to go from here. This problem has bugged me for a long time - I'm sure there's something I can do with these "counts of "powers mod 250"" - but everything I think of implies a prohibitive run time so I'm missing something!

Thanks,

Will (Hippunky).

[sivakd]

Did you solve Problem 249? Solve one, and you will be able to solve the other with minimal effort.

[Hippunky]

Hi Sivakd - yes, I did (eventually) solve 249, am not sure my solution will scale to 250250 elements, but perhaps I've dismissed that out of hand - I'll give it a try and will let you know how it goes.

Thanks!

Will.

[Hippunky]

The approach I took to problem 249 doesn't scale to problem 250, at least not yet.

I hope the below isn't considered a spoiler as it's prohibitively slow!

My approach to 250 thus far has been:

Perform (x^x) Mod 250 for all of the numbers. Maintain a set of the resultant values together with the number of times each value appears, e.g. {(0, 25025), (1, 1001), (3, 1001), ...}.

I iterate over this set of mod-freq pairs, for each pair (a, b) adding a * 1, 2, 3, ..., b to all sums achieved for lower values of a - and maintaining the frequency by using nCr * "frequency of earlier sum" (nCr is optimized to be really fast - the calculation of nCr (mod 1e16) isn't the bottleneck). My bottleneck is calculating (nCr * "frequency of earlier sum") mod 1e16 - as nCr and the freq. are both 64-bits - but I feel that even if I remove this bottleneck, the approach will still be really slow.

Should I instead be looking for an approach that answers the question 'how many ways can 250*x be written using 25025 0's, 1001 1's, 1001 3's, etc.' in a quick manner?

Any hints (no spoilers, please!) much appreciated!

Regards,

Will.

[sivakd]

Will, check the private forum for 249 to get some ideas on other ways of solving this type of problems.

[Hippunky]

D'oh - fantastic idea - sorry, hadn't even considered this. Thanks!

[psujono]

Problem 250 (View Problem)
What exactly is meant by "non-empty subsets"

[hk]

An empty set is a set with no elements.
So a non-empty set has at least one element.


A non empty subset of {1^1, 2^2, 3^3,..., 250250^250250} has at least one element of the form a^a with a from 1..250250.
See also Subset

[thkang]

I solved problem 249 and 250 with same method, only tweaking parameters.

249 was the problem I solved first, but my method worked better and faster for 250, since only 250 values are stored in my array, compared to 1450000 values for 249.

Both problems are good and if you know more about modular arithmetic and so(unfortunately I'm not), you might be able to come up with solutions better than mine!

[yourmaths]

I just solved 249 and 250. While 249 is probably easier to understand, 250 is (can be?!) definitely the easier problem computationally!

[enigmaticcam]

Suppose I have a set that totals to 250, say {1^1 + 249^249}. Would there exist a similar set with a zero, say {1^1 + 249^249 + 250^250}? In fact, since there are 25,025 ways where x^x % 250 = 0, then for any set that total to 250 that doesn't have any zeros, there exist many other sets that use the same elements plus all combinations of elements that sum to 0? Is that correct?

[LilStalker]

Yes, that is correct.