This post has been edited by **Python_4_President**: 01 November 2012 - 09:09 AM

## 26 Replies - 8519 Views - Last Post: 10 November 2012 - 11:17 AM

### #16

## Re: Halloween Python Challenge

Posted 01 November 2012 - 08:30 AM

### #17

## Re: Halloween Python Challenge

Posted 02 November 2012 - 01:32 AM

**Updated code**

This post has been edited by **blackcompe**: 02 November 2012 - 06:51 PM

### #18

## Re: Halloween Python Challenge

Posted 02 November 2012 - 02:30 AM

Test cases are a good idea. I will have to update the first post later, so check back!

### #19

## Re: Halloween Python Challenge

Posted 02 November 2012 - 03:18 PM

115:false 116:true 117:true 118:true 119:true 120:true 121:true (115,120)

It appears that this algorithm doesn't generalize at all. The only problem that's correctly solved is this the particular case of 6, 9, and 20. Heh, maybe that's what was intended. I also found a calculator for the Frobenius problem (McNuggets generalized).

This post has been edited by **blackcompe**: 02 November 2012 - 03:19 PM

### #20

## Re: Halloween Python Challenge

Posted 02 November 2012 - 03:28 PM

If you're talking about the six consecutive numbers, the generalization for that is, taking x to be the least term in the set, if you have x consecutive numbers then any number above that point must be a solution. Easy to prove: if p is a solution, then p+x is a solution. If xa + yb +c = p, then x(a+1) +yb+zc = p+x.

So in this case you need to look for 9 consecutive solutions.

### #21

## Re: Halloween Python Challenge

Posted 02 November 2012 - 03:32 PM

Quote

Ah thanks Jon!

**Edit:**

I got it working.

This post has been edited by **blackcompe**: 02 November 2012 - 03:39 PM

### #22

## Re: Halloween Python Challenge

Posted 05 November 2012 - 08:26 PM

There's an obvious improvement to make, of course - testing for GCD at the outset would tidy things up a little. However, the question of what number constitutes a reasonable upper bound is an interesting one, so I wanted to leave it in place while I think it over.

### #23

## Re: Halloween Python Challenge

Posted 06 November 2012 - 08:51 AM

Quote

Can you expand on this? Perhaps give an example? When you say

*known solution*, are you referring to a number that we find can (or can't) find a solution for? For instance, in the McNugget problem, the numbers that don't have solutions are:

1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43

So are the

*known solutions*the complement of that set?

Secondly, what's x referring to here when you say "modulo x". Is it the a coefficient in the equation (e.g. 6 for the McNugget problem) or is it the value of the unknown x in the equation for that particular solution.

E.g. In finding a solution for N = 42 in the McNugget problem, we have:

6 * x + 9 * y + 20 * z = 42

A solution is [x = 7, y = 0, z = 0]

So the x you're referring to is then 7. So we'd have something like this:

42 = test_number (mod 7)

Obviously, there's no test_number that satisfies that congruence, so I know my logic is incorrect, but is this close to what you mean?

### #24

## Re: Halloween Python Challenge

Posted 06 November 2012 - 11:56 AM

Quote

By "a known solution" I mean some number which is known to be a possible solution to that equation. So 42, as you say, is known to be a possible solution (and therefore 49 is as well)

The set of known solutions would be, as you say, the complement of the set of numbers which cannot be solutions.

Quote

Yes, I mean the "a" coefficient. Sorry, that was unclear. Particularly, I mean the least of the coefficients. So perhaps I should have said "a". That would have made more sense.

So from your example, if we know that 42 is a legitimate "move" in this game, then we can infer that 48, as well as 51, and 62, are legal moves. This is a simple rule of inference which in a way ignores the math of it, but it turns out to be correct, as we saw above.

In fact, we could reduce this to a simple nim-type "game", though not a very entertaining one. The rules are, you start from zero, and you can derive any number which you can reach by adding some member of the coefficient set. If you imagine a grid of "x" (a, really! ) rows, numbered 0..x-1 and filled in with the numbers in the obvious pattern (0..x-1, x..2x-1, etc), extending arbitrarily far to the right, you can imagine the goal being to "claim" rows by deriving the lowest possible number in that row, according to the simple rule of derivation.

My algorithm, basically, plays this game as a solitaire.

That game, by the way, is an example, or perhaps an illustration, of my assertion that "we don't need to test numbers which are congruent modulo x to a known solution." it should be obvious that once we reach any square on that grid, all of the squares to the right of it are known to be solutions. Therefore, finding the least value in each row, and then taking the largest of that set, is sufficient to solve the problem.

This post has been edited by **jon.kiparsky**: 06 November 2012 - 12:01 PM

### #25

## Re: Halloween Python Challenge

Posted 06 November 2012 - 05:02 PM

Quote

So from your example, if we know that 42 is a legitimate "move" in this game, then we can infer that 48, as well as 51, and 62, are legal moves.

I'm still unclear. Can you show the Math behind finding that 48, 51, and 62 are solutions. From what I understand, your saying (for the McNugget problem, where a = 6):

0 = 48 mod 6

3 = 51 mod 6

2 = 62 mod 6

0, 3, 2 are previously found known solutions, but for

1 = 43 mod 6

1 is a known solution, and therefore 43 is a known solution, which is obviously not true.

### #26

## Re: Halloween Python Challenge

Posted 06 November 2012 - 11:44 PM

Okay, I admit that I've had a few beers at this point (happy re-election to all!) but there's three steps as I see it.

First of all, zero is a solution to any equation of this form. (see above)

Second, if the coefficients of the equation are listed as (a, b, c...) then any previously derived solution, increased by some member of that set, is also a solution.

Third, if we have a solution in row of this notional grid, described above, then we know that there is a point above which all integers are solutions to this equation.

I think each of these is proveable, and I think that

Fourth, taken together they establish that the algorithm is sound.

I would be happy to try to walk through any of these tomorrow evening, when I'm not at work and when I'm not just back from the bar. Let me know which you'd like.

### #27

## Re: Halloween Python Challenge

Posted 10 November 2012 - 11:17 AM

I did play around with upper bounds. I tried to guestimate that since the solution is coprime to all the coefficients, and the Sieve of Eratosthenes is O(n^1.5), then the upper bounds for the largest non-solution is (sum of coefficients)^1.5. Unfortunately, that didn't scale. The lower bounds I found was sqrt(3 * product(coefficients)) - (Sum of coefficients). My lower bounds was more efficient. Given the equation 77x + 42y = c, sqrt(3*77*42) - (77+42) < 0, and my lower bounds is 41 there.

This post has been edited by **Simown**: 10 November 2012 - 07:14 PM

Reason for edit:: Code tags?!