# Markus' lucky numbers

It was late night when Markus was sitting at his desk and suddenly a fairy appeared out of nowhere. She told him that he had been granted a wish. Markus wished for her to tell him next week's lottery draw and handed her pen and paper. But the fairy told him that these were 6 wishes and that thus it was not possible for her to tell him. Instead she wrote one number on the paper and said: "This is the sum of all of next week's numbers in the lottery draw." Markus then thought There are too many possibilites for me to just guess the numbers. The fairy, who had sensed his thoughts then gave him another tip: "The number of possibilites that this sum can be achieved multiplied with it is a really big number, in the magnitude of a few million $(number >= 10,000,000)$, and it is also equal to the product of the six numbers." After she had vanished, Markus began to scribble and sure enough, won the lottery the next week.

What are the six numbers?

The solution is unique.

TL;DR

• Six distinct numbers between including 1 and 49 - for you maths people: $[1,49]$
• Sum of these times possibilities of summands is equal to product of these numbers and >= 10,000,000.
• Is it (1,49) or [1,49] – Hubble07 Aug 20 '14 at 17:42
• @Hubble07 [1,49], like lottery in general – ThreeFx Aug 20 '14 at 17:47
• Would you happen to know a more elegant way of solving this problem than simply throwing clock cycles at it? – aaaaaaaaaaaa Aug 31 '14 at 20:07

I'd guess the answer is 130, based on output from the following python program. There are 140008 ways to make the sum 130, and the tuple (5, 8, 11, 26, 37, 43) has sum 130, product 18201040, and 130 times 140008 is 18201040.

Here's the python program, followed by its output:

#!/usr/bin/env python
# Re: http://puzzling.stackexchange.com/questions/2119/markus-lucky-numbers
# Find: Six distinct numbers from [1,49] such that their sum, times
# the number of possible ways to get that sum, is equal to their
# product, which is >= 10,000,000.

from itertools import combinations
from operator import mul

u = range(1,50)
maxSum = 44+45+46+47+48+49
ways = [0]*(maxSum+1)
for c in combinations(u, 6):
s = sum(c)
ways[s] += 1

for c in combinations(u, 6):
s = sum(c)                  # Get sum of #'s
p = reduce(mul, c, 1)       # Get product of #'s
w = ways[s]                 # Get # of ways to make sum
if s*w == p:
print s, w, p, c


It took 0m14.775s to run, and produced the following output:

36 110 3960 (1, 2, 3, 4, 11, 15)
45 532 23940 (1, 4, 5, 7, 9, 19)
76 13552 1029952 (2, 8, 11, 14, 19, 22)
130 140008 18201040 (5, 8, 11, 26, 37, 43)

• Correct, sir! :D – ThreeFx Aug 20 '14 at 20:05

I couldn't find a trick to solve this because I don't know a formula for "possibilities of summands." So I wrote a program and tried to brute force a solution. There turn out to be many or I am mistaken...

Let's go step by step. Suppose the sum is 21 there is only one possible drawing: 1,2,3,4,5,6. The order of the numbers drawn doesn't matter, since the question is about finding the correct numbers to place the bet on.

For a sum of 22 the numbers are 1,2,3,4,5,7. Again a unique solution. For sum=23 it could be either 1,2,3,4,5,8 or 1,2,3,4,6,7. I let the computer calculate and came to this list (shortened)

20 --> P=0;
21 --> P=1;
22 --> 1; 23 --> 2; 24 --> 3; 25 --> 5; 26 --> 7; 27 --> 11; 28 --> 14; 29 --> 20; 30 --> 26; 31 --> 35; 32 --> 44; 33 --> 58; 34 --> 71; 35 --> 90; ...

For sum=35 there are already multiple solutions. Given the "probability of summands" above (P=90), possible solutions are:

1 2 3 4 5 45: 1*2*3*4*5*45 = 5400 = 90 * 60 = 90 * (1+2+3+4+5+45)

1 2 3 4 10 12: 1*2*3*4*10*12 = 2880 = 90 * 32 = 90 * (1+2+3+4+10+12)

Other examples: 1 2 3 5 6 17; 1 2 3 5 9 10; 1 2 4 5 7 9

Given the wording of the puzzle, I'd have expected a unique solution. Is the wording of the puzzle correct?

• The solution is unique, I'll add it in a sec. Alright, it should be correct now. – ThreeFx Aug 20 '14 at 18:14
• Just to be sure: is this a pen and paper or computational puzzle? – user3883664 Aug 20 '14 at 18:33
• Both should be possible, depending on how good your mental maths skills are. :P – ThreeFx Aug 20 '14 at 18:35
• You added the information about the 2nd number being "larger than a few million". What is the lower base for a few million? 2.000.000? 3.000.000? Because after brute force there are still plenty of solutions with product > 1.000.000 ... – user3883664 Aug 20 '14 at 18:55
• An unoptimised, poorly written brute force will need about 16 seconds, so do not wonder about this limit. Just to set it: 1,000,000 – ThreeFx Aug 20 '14 at 18:57