A customer at a 7-11 store selected four items to buy, and was told that the cost was $7.11.
arithmetic/7-11 Added material
Problem
A customer at a 7-11 store selected four items to buy, and was told that the cost was $7.11. He was curious that the cost was the same as the store name, so he inquired as to how the figure was derived. The clerk said that he had simply multiplied the prices of the four individual items. The customer protested that the four prices should have been ADDED, not MULTIPLIED. The clerk said that that was OK with him, but, the result was still the same: exactly $7.11. What were the prices of the four items?
Show solution
The prices are: $1.20, $1.25, $1.50, and $3.16
$7.11 is not the only number which works. Here are the first 160 such
numbers, preceded by a count of distinct solutions for that price.
Note that $7.11 has a single, unique solution.
1 - $6.44 1 - $7.83 2 - $9.20 3 - $10.89
1 - $6.51 1 - $7.86 1 - $9.23 1 - $10.95
1 - $6.60 3 - $7.92 1 - $9.24 2 - $11.00
1 - $6.63 1 - $8.00 1 - $9.27 1 - $11.07
1 - $6.65 1 - $8.01 2 - $9.35 1 - $11.13
1 - $6.72 1 - $8.03 3 - $9.36 1 - $11.16
2 - $6.75 5 - $8.10 1 - $9.38 1 - $11.22
1 - $6.78 1 - $8.12 5 - $9.45 2 - $11.25
1 - $6.80 1 - $8.16 2 - $9.48 2 - $11.27
2 - $6.84 2 - $8.19 1 - $9.54 1 - $11.30
1 - $6.86 1 - $8.22 1 - $9.57 1 - $11.36
1 - $6.89 1 - $8.25 1 - $9.59 1 - $11.40
2 - $6.93 3 - $8.28 2 - $9.60 2 - $11.43
1 - $7.02 3 - $8.33 1 - $9.62 2 - $11.52
1 - $7.05 1 - $8.36 2 - $9.63 2 - $11.55
2 - $7.07 1 - $8.37 1 - $9.66 2 - $11.61
1 - $7.08 2 - $8.40 1 - $9.68 1 - $11.69
1 - $7.11 1 - $8.45 2 - $9.69 1 - $11.70
1 - $7.13 2 - $8.46 1 - $9.78 1 - $11.88
2 - $7.14 1 - $8.52 2 - $9.80 1 - $11.90
3 - $7.20 5 - $8.55 1 - $9.81 1 - $11.99
1 - $7.25 1 - $8.60 1 - $9.87 1 - $12.06
1 - $7.26 4 - $8.64 4 - $9.90 1 - $12.15
2 - $7.28 1 - $8.67 1 - $9.92 1 - $12.18
1 - $7.29 1 - $8.69 2 - $9.99 1 - $12.24
3 - $7.35 1 - $8.73 1 - $10.01 1 - $12.30
1 - $7.37 2 - $8.75 1 - $10.05 1 - $12.32
1 - $7.47 1 - $8.76 2 - $10.08 1 - $12.35
1 - $7.50 1 - $8.78 1 - $10.17 2 - $12.42
1 - $7.52 5 - $8.82 1 - $10.20 1 - $12.51
4 - $7.56 1 - $8.85 2 - $10.26 1 - $12.65
1 - $7.62 1 - $8.88 3 - $10.29 2 - $12.69
4 - $7.65 2 - $8.91 3 - $10.35 1 - $12.75
1 - $7.67 1 - $8.94 2 - $10.44 1 - $12.92
2 - $7.70 1 - $8.96 1 - $10.53 1 - $12.96
3 - $7.74 3 - $9.00 1 - $10.56 1 - $13.23
1 - $7.77 1 - $9.02 1 - $10.64 1 - $13.41
1 - $7.79 2 - $9.03 2 - $10.71 1 - $13.56
2 - $7.80 1 - $9.12 3 - $10.80 1 - $14.49
1 - $7.82 2 - $9.18 1 - $10.85 1 - $15.18
There are plenty of solutions for five summands. Here are a few:
$8.28 -- at least two solutions
$8.47 -- at least two solutions
$8.82 -- at least two solutions
--
Mark Johnson mark@microunity.com (408) 734-8100
There may be many approximate solutions, for example: $1.01, $1.15, $2.41,
and $2.54. These sum to $7.11 but the product is 7.1100061.
Additional material
[ Editor: on the case of real-valued prices: ]
You'll get similar equations regardless of whether there is tax included.
Depending on whether you insist on the discreteness of prices (as integer
multiples of $0.01), there will be either *no* solutions, or *uncountably
many* solutions. In the latter case, the problem might then be how to
describe the infinitely many solutions.
[ Editor: the discrete case does have a solution, given above:
1.20 + 1.25 + 1.50 + 3.16 = 7.11 and 1.20 * 1.25 * 1.50 * 3.16 = 7.11. ]
(Eq1) A+B+C+D=$7.11
(Eq2) A*B*C*D=$7.11
For the continuous case, choose numbers (x,y) to be such
that -7.10<x<7.10 and 0<y<oo, and write:
(Eq3) A+B=C+D+x
(Eq4) A*B=C*D*y
Then the original eqns become
(Eq1) 2(A+B)=7.11+x [Editor: "7.11-x" in the original]
(Eq2) (A*B)^2=7.11*y [Editor: "7.11/y" in the original]
Using Eq2 to write A in terms of B, and substituting in Eq1, we get
A + sqrt(7.11*y)/A = (7.11+x)/2 [Editor: "sqrt(7.11/y)" and "(7.11-x)/2" in the original]
and simplifying,
A^2 - [(7.11+x)/2]A + sqrt(7.11*y) = 0 [Editor: "(7.11-x)/2" and "sqrt(7.11/y)" in the original]
Solve this quadratic for A, then get B from Eq1 (or Eq2). (You can write
these out explicitly in terms of square roots, of course.) Denote these
as A=A(x,y) and B=B(x,y) (I believe the two quadratic solutions for A
will turn out to include the solution for B.)
Note: This quadratic has no rational solutions, justifying the claim that
in the discrete case there are no solutions.
[ Editor: as shown above, the discrete case has the solution 1.20, 1.25,
1.50, 3.16, so this claim is mistaken. ]
We now have from Eq3 & Eq4
(Eq5) C+D=S, where S=A+B-x (known)
(Eq6) C*D=P, where P=AB/y (known)
giving C+P/C=S, or C^2-S*C+P=0, which is another quadratic that can be
solved explicitly for C, and then D is determined from Eq5 or Eq6.
(Again, I believe that the two quadratic solutions will include the
solution for C.) These can be denoted C=C(x,y) and D=D(x,y).
You now have a solution (A,B,C,D)=(A(x,y), B(x,y), C(x,y), D(x,y)) for
the chosen (x,y),
To recap: If prices are not restricted to discrete values, then there
are infinitely many solutions (A,B,C,D) satisfying Eq1 and Eq2, as given
above, and by varying the independent parameters (x,y) in the range
specified above, all the solutions are described.
-- Robert E Sawyer <soen@pacbell.net>
[ Editor: from a September 1994 rec.puzzles thread "$7.11 problem
extended", and a mail from Jim Gillogly to Chris Cole of November 1994. ]
Andrew F. Loughe <andy@pong.gsfc.nasa.gov> wrote:
> The answer I know. The general solution method I do not know.
Factor 711,000,000 and check sums of different combinations of the
factors.
[ Editor: Gillogly then added: ]
I'm afraid that was a bit glib. I programmed it up and it takes almost
as long as the brute force method: 18 seconds on my laptop instead of
30. Maybe I've missed some optimizations. Anybody have a faster way to
do it? You can use my handy-dandy new factoring program, if that helps:
void factor(n) /* By trial division */
unsigned long n;
{
unsigned long i;
for (i = 2; i * i < n; i = i == 2? 3 : i + 2)
for (; i * (n / i) == n; n /= i)
factors[nfactors++] = i;
factors[nfactors++] = n;
}
In any case, I'll atone for the glibness by extending the puzzle:
The next day he walked into the 7-11, selected 5 items, no two of them
the same, and none under a dime (got to eliminate the other 4 solutions
somehow!), and checked out. Same as before: the clerk charged him
$7.11, which he got by multiplying the prices... also as before, they
added up to $7.11 anyway. What were the prices?
I'll assert that there are 16 solutions for the 6-item version, for the
masochistic puzzlers amongst you, starting with $.01 $.01 $.79 $1.80
$2.00 and $2.50, and ending with $.04 $.06 $.06 $.50 $2.50, and $3.95.
-- Jim Gillogly <jim@acm.org> (September 1994)
In <358coo$2ga@mycroft.rand.org> Jim Gillogly <jim@acm.org> tried
extending the puzzle to 5 or 6 items, later retracting his results in
<35aban$3lj@mycroft.rand.org>.
If you have 5 real numbers whose sum and product are both equal to
7.11, then their arithmetic mean (or average) is 7.11/5 = 1.422, and
their geometric mean is (7.11)^(1/5) = 1.4804 is larger.
(For the uninitiated, the geometric mean of n positive real
numbers is defined to be the n-th root of their product.)
However, a classical mathematical result (the famous "AM-GM
inequality") says that the arithmetic mean is always greater than (or
equal to) the geometric mean. So such a set of 5 real numbers cannot
exist, even without the restriction that they must be
"dollars-and-cents" amounts. The cases of 6 or more items also have no
solutions, for the same reason.
This puzzle is called "Alice and the Mad Adder" in the book "Ingenious
Mathematical Problems and Methods", by L. A. Graham. It was published
as a paperback by Dover in 1959.
-- Barry Wolk <wolk@ccm.UManitoba.CA> (September 1994)
[ Editor: Gillogly's mail to Chris Cole, November 1994: ]
I did a bunch of 7-11 runs a month or so ago and haven't updated you.
There are some problems with the solutions in the Archive, so hopefully
these will fix 'em.
I've extended it in both directions. Turns out it's harder to compute
for the higher numbers, but there are more solutions there. Here are
all the numbers of solutions for 2 and 3 under $20.00, 4-7 under $10.00,
and the first few for 8.
My "Help name my store" extension was:
So -- if I were to start a store across the street from the 7-11,
what's the lowest number I could name it so that there <is> a solution
for sets of both four and five prices? The second lowest such name
would be 7-65 (with prices $1.20/$1.25/$1.50/$1.70/$2.00 and
$0.60/$2.00/$2.50/$2.55 (eg)) but we strive for optimality around here,
especially in matters such as this.
The answer is 7-62, and the answers are
4: 100 127 160 375
5: 125 127 150 160 200
Turns out there's one that works for all of 2-8: $14.58, which makes it
special. I conjecture that it works for everything from there up,
also, but I run out of bits after 8.
2: 108 1350
3: 45 288 1125
4: 18 240 450 750
5: 18 90 400 450 500 (and many others)
6: 8 225 240 250 360 375 (and many many others)
7: 8 160 250 250 250 270 270 (ditto)
8: 12 96 200 200 225 225 250 250 (ditto)
There are a number of errors in the Archive entry as it gets near the
top; I suspect the numbers started overflowing before the author
noticed it. I used long longs with gcc. I append the program after
the data... I think my factoring routine is quite cute.
2:
1 - $4.00 1 - $4.90 1 - $8.41
1 - $4.05 1 - $6.25 1 - $12.10
1 - $4.50 1 - $7.20 1 - $14.58
3:
1 - $5.25 1 - $7.50 2 - $10.50 1 - $13.80 1 - $17.40
1 - $5.40 1 - $7.59 1 - $10.71 1 - $14.04 2 - $17.55
1 - $5.46 1 - $7.65 1 - $10.80 1 - $14.10 1 - $17.88
1 - $5.49 1 - $7.83 1 - $10.92 1 - $14.19 2 - $18.48
1 - $5.55 1 - $7.92 1 - $11.25 1 - $14.49 1 - $18.75
1 - $5.61 1 - $7.98 1 - $11.34 1 - $14.58 1 - $19.11
1 - $5.67 1 - $8.10 2 - $11.55 1 - $14.76 1 - $19.35
1 - $5.70 1 - $8.19 1 - $11.70 1 - $14.79 1 - $19.47
1 - $5.85 1 - $8.25 1 - $11.85 2 - $14.82 1 - $19.95
1 - $5.88 2 - $8.40 1 - $11.97 1 - $15.00
1 - $6.00 1 - $8.91 1 - $12.06 1 - $15.45
1 - $6.12 1 - $8.97 1 - $12.21 1 - $15.60
1 - $6.30 1 - $9.00 1 - $12.45 1 - $15.66
1 - $6.42 1 - $9.30 1 - $12.72 1 - $15.75
2 - $6.60 1 - $9.45 1 - $12.81 1 - $15.90
1 - $6.63 1 - $9.57 1 - $13.14 1 - $15.96
1 - $6.75 2 - $9.66 1 - $13.20 1 - $16.02
1 - $7.26 1 - $9.75 1 - $13.26 1 - $16.50
1 - $7.35 1 - $9.81 1 - $13.53 1 - $16.65
1 - $7.44 1 - $9.96 1 - $13.65 3 - $17.22
4:
1 - $6.44 3 - $7.35 1 - $8.22 3 - $9.00 1 - $9.78
1 - $6.51 1 - $7.37 1 - $8.25 1 - $9.02 2 - $9.80
1 - $6.60 1 - $7.47 3 - $8.28 2 - $9.03 1 - $9.81
1 - $6.63 1 - $7.50 3 - $8.33 1 - $9.12 2 - $9.86
1 - $6.65 1 - $7.52 1 - $8.36 2 - $9.18 2 - $9.87
1 - $6.72 4 - $7.56 1 - $8.37 2 - $9.20 1 - $9.89
2 - $6.75 1 - $7.62 2 - $8.40 1 - $9.23 5 - $9.90
1 - $6.78 4 - $7.65 1 - $8.45 1 - $9.24 1 - $9.92
1 - $6.80 1 - $7.67 2 - $8.46 1 - $9.27 4 - $9.99
2 - $6.84 2 - $7.70 1 - $8.52 2 - $9.35
1 - $6.86 3 - $7.74 5 - $8.55 3 - $9.36
1 - $6.89 1 - $7.77 1 - $8.60 1 - $9.38
2 - $6.93 1 - $7.79 4 - $8.64 5 - $9.45
1 - $7.02 2 - $7.80 1 - $8.67 2 - $9.48
1 - $7.05 1 - $7.82 1 - $8.69 1 - $9.54
2 - $7.07 1 - $7.83 1 - $8.73 1 - $9.57
1 - $7.08 1 - $7.86 2 - $8.75 1 - $9.59
1 - $7.11 3 - $7.92 1 - $8.76 3 - $9.60
1 - $7.13 1 - $8.00 1 - $8.78 1 - $9.62
2 - $7.14 1 - $8.01 5 - $8.82 2 - $9.63
3 - $7.20 1 - $8.03 1 - $8.85 2 - $9.66
1 - $7.25 5 - $8.10 1 - $8.88 1 - $9.68
1 - $7.26 1 - $8.12 2 - $8.91 2 - $9.69
2 - $7.28 1 - $8.16 1 - $8.94 1 - $9.72
1 - $7.29 2 - $8.19 1 - $8.96 1 - $9.75
5:
1 - $7.59 2 - $8.22 2 - $8.75 2 - $9.25 3 - $9.73
1 - $7.60 3 - $8.25 2 - $8.76 1 - $9.27 4 - $9.75
1 - $7.62 1 - $8.26 3 - $8.80 1 - $9.28 2 - $9.76
1 - $7.65 3 - $8.28 11 - $8.82 3 - $9.30 2 - $9.78
2 - $7.70 1 - $8.32 2 - $8.84 5 - $9.31 2 - $9.79
1 - $7.74 5 - $8.33 3 - $8.88 5 - $9.35 9 - $9.80
1 - $7.77 2 - $8.34 2 - $8.89 8 - $9.36 2 - $9.81
1 - $7.79 3 - $8.36 9 - $8.91 2 - $9.38 2 - $9.84
3 - $7.80 2 - $8.37 1 - $8.93 2 - $9.40 5 - $9.86
2 - $7.83 8 - $8.40 2 - $8.94 3 - $9.42 5 - $9.87
1 - $7.84 1 - $8.41 2 - $8.96 1 - $9.43 3 - $9.88
1 - $7.85 3 - $8.45 6 - $8.97 1 - $9.44 4 - $9.89
1 - $7.86 1 - $8.46 6 - $9.00 31 - $9.45 19 - $9.90
2 - $7.91 6 - $8.47 3 - $9.01 2 - $9.46 3 - $9.92
3 - $7.92 1 - $8.48 2 - $9.02 2 - $9.48 3 - $9.94
1 - $7.95 2 - $8.50 5 - $9.03 1 - $9.50 3 - $9.96
5 - $7.98 1 - $8.51 1 - $9.04 4 - $9.52 8 - $9.99
2 - $7.99 3 - $8.52 3 - $9.06 6 - $9.54
1 - $8.00 2 - $8.54 1 - $9.08 1 - $9.56
2 - $8.04 4 - $8.55 2 - $9.09 2 - $9.57
3 - $8.05 5 - $8.58 10 - $9.10 2 - $9.59
1 - $8.06 1 - $8.60 4 - $9.12 6 - $9.60
1 - $8.08 1 - $8.61 1 - $9.13 1 - $9.61
8 - $8.10 6 - $8.64 2 - $9.15 2 - $9.62
2 - $8.12 4 - $8.67 2 - $9.17 1 - $9.63
1 - $8.13 2 - $8.68 15 - $9.18 6 - $9.66
3 - $8.16 1 - $8.69 2 - $9.20 2 - $9.68
3 - $8.17 1 - $8.70 1 - $9.21 7 - $9.69
8 - $8.19 1 - $8.71 2 - $9.23 1 - $9.70
1 - $8.20 2 - $8.74 9 - $9.24 11 - $9.72
6:
1 - $8.64 2 - $9.02 2 - $9.38 5 - $9.69
1 - $8.68 3 - $9.03 1 - $9.40 20 - $9.72
1 - $8.69 2 - $9.04 4 - $9.42 2 - $9.73
1 - $8.73 2 - $9.06 1 - $9.43 7 - $9.75
1 - $8.75 1 - $9.09 2 - $9.44 2 - $9.78
1 - $8.76 4 - $9.10 30 - $9.45 5 - $9.79
1 - $8.80 4 - $9.12 3 - $9.46 6 - $9.80
6 - $8.82 1 - $9.13 4 - $9.48 1 - $9.81
2 - $8.84 1 - $9.15 1 - $9.49 4 - $9.84
1 - $8.85 9 - $9.18 2 - $9.50 3 - $9.86
1 - $8.88 3 - $9.20 6 - $9.52 8 - $9.87
1 - $8.89 1 - $9.23 5 - $9.54 3 - $9.88
7 - $8.91 8 - $9.24 1 - $9.55 2 - $9.89
1 - $8.93 1 - $9.25 7 - $9.57 20 - $9.90
1 - $8.94 2 - $9.27 6 - $9.60 2 - $9.92
1 - $8.96 2 - $9.28 1 - $9.61 3 - $9.94
2 - $8.97 2 - $9.30 2 - $9.62 5 - $9.96
2 - $8.99 6 - $9.31 2 - $9.63 11 - $9.99
5 - $9.00 3 - $9.35 11 - $9.66
1 - $9.01 6 - $9.36 3 - $9.68
7:
1 - $9.72 2 - $9.84 1 - $9.90 4 - $9.99
1 - $9.75 1 - $9.85 1 - $9.94
1 - $9.78 1 - $9.88 1 - $9.96
8:
3 - $10.89
2 - $10.92
1 - $10.98
-- Jim Gillogly <jim@acm.org> (November 1994)
[ Editor: the mail ends with the C program (711c) that produced these
tables: ]
/* #define VERBOSE */
/* 711c: do the 7.11 puzzle by recursive factoring and enumeration
* SCRYER, Sep 94
*/
#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long mega;
#define MAXTARGET 5000 /* Or so */
#define MAXVALS 500 /* How many prices can we make with these factors? */
#define MAXPRICES 8 /* Run into long long overflow after this */
int PRICES; /* How many prices do we want to fit? */
#define MAXFACTORS 50
void factor(mega n, mega *factors, int *nfactors);
void value_check(mega target, int index, mega sofar, char *used, mega *values, int *nvalues, mega *factors, int *counts);
void consistency(mega target, mega multarget, int index, mega *values, int nvalues, int prices);
mega sub_sum(), sub_product();
void recurse(mega target, mega multarget, int prices);
mega sub_sum(int index, int prices);
mega sub_product(int index, int prices);
int compare();
main(int argc, char *argv[])
{
int i, j;
mega from, to, target, multarget;
if (argc != 4)
{
printf("Usage: 711c <# prices> <from> <to>\n");
return 1;
}
PRICES = atoi(argv[1]);
if (PRICES > MAXPRICES)
{
fprintf(stderr, "Can't hack that many prices.\n");
return 1;
}
from = atol(argv[2]);
to = atoi(argv[3]);
for (target = from; target <= to; target++)
{
for (i = 1, multarget = target; i < PRICES; i++)
multarget *= 100;
printf("%Ld\n", target);
recurse(target, multarget, PRICES);
fflush(stdout);
}
return 0;
}
mega price[MAXPRICES];
void recurse(mega target, mega multarget, int prices)
{
char used[MAXTARGET];
mega factors[MAXFACTORS]; /* What's the next factor? */
int counts[MAXFACTORS]; /* How many of this factor are there? */
int nfactors = 0;
mega values[MAXVALS];
int nvalues = 0;
mega sofar;
int i, j;
if (prices == 1) /* Just the one price */
{
if (target == multarget)
{
price[0] = target;
printf("Winner:");
for (i = 0;i < PRICES; i++)
printf(" %Ld", price[i]);
printf("\n");
}
}
else
{
/* printf("Recurse: %Ld %Ld\n", target, multarget); */
factor(multarget, factors, &nfactors);
/* Consolidate factors -- we could do this in factor() */
for (i = 1, j = 0, counts[0] = 1; i < nfactors; i++)
if (factors[i] == factors[j]) counts[j]++;
else
{
factors[++j] = factors[i];
counts[j] = 1;
}
nfactors = j + 1;
#ifdef VERBOSE
printf("%Ld: %d factors:", target, nfactors);
for (i = 0; i < nfactors; i++)
printf(" %Ld^%d", factors[i], counts[i]);
printf("\n");
#endif
for (i = 0; i < MAXTARGET; i++) used[i] = 0;
sofar = 1;
value_check(target, nfactors - 1, sofar, used, values, &nvalues, factors, counts); /* See what values there could be */
qsort(values, nvalues, sizeof (mega), compare);
#ifdef VERBOSE
printf("%d possible values: ", nvalues);
for (i = 0; i < nvalues; i++)
printf(" %Ld", values[i]);
printf("\n");
#endif
consistency(target, multarget, prices - 1, values, nvalues, prices);
}
}
void value_check(mega target, int index, mega sofar, char *used, mega *values, int *nvalues, mega *factors, int *counts) /* See what values are legal */
{
int i;
mega prod;
if (index < 0) return; /* Finished */
if (sofar >= target) return; /* Sum means none this big */
if (index > 0)
{
value_check(target, index - 1, sofar, used, values, nvalues, factors, counts); /* Might have none of this factor */
for (i = 0; i < counts[index]; i++) /* or any other number */
{
sofar *= factors[index];
value_check(target, index - 1, sofar, used, values, nvalues, factors, counts);
}
return;
}
if (!used[sofar])
{
values[(*nvalues)++] = sofar;
used[sofar] = 1;
}
for (i = 0; i < counts[index]; i++)
{
sofar *= factors[index];
if (sofar < target && ! used[sofar])
{
values[(*nvalues)++] = sofar;
used[sofar] = 1;
}
}
}
void consistency(mega target, mega multarget, int index, mega *values, int nvalues, int prices) /* Assign a value to this index and try others */
{
int i, j, k;
mega sum, product, subsum, subprod;
#ifdef VERBOSE
printf("consistency(%d): ", index);
for (i = 0; i < PRICES; i++)
if (i > index) printf(" %Ld", price[i]);
else printf(" --");
printf("\n");
#endif
subsum = sub_sum(index + 1, prices);
subprod = sub_product(index + 1, prices);
#ifdef VERBOSE
if (subsum > target) printf("subsum %Ld > target %Ld - returning.\n",
subsum, target);
if (subprod > multarget) printf("subprod %Ld > multarget %Ld - returning.\n",
subprod, multarget);
#endif
if (subsum > target) return;
if (subprod > multarget) return;
for (i = 0; i < nvalues; i++)
{
/* Step out of the recursion to make sure we're in increasing order */
if (index != PRICES - 1 && values[i] > price[index + 1]) break;
if (subsum + (index + 1) * values[i] < target) continue;
price[index] = values[i];
/* Now recurse with modified target and multarget */
/* consistency(target, multarget, index - 1, values, nvalues); */
#ifdef VERBOSE
printf("Trying value %Ld in position %d; new targets %Ld and %Ld\n",
price[index], index, target - price[index], multarget / price[index]);
#endif
recurse(target - price[index], multarget / price[index], prices - 1);
}
}
mega sub_sum(int index, int prices) /* Sum so far */
{
int i;
mega sum;
for (i = index, sum = 0; i < prices; i++)
sum += price[i];
return sum;
}
mega sub_product(int index, int prices) /* Product so far */
{
int i;
mega product;
for (i = index, product = 1; i < prices; i++)
product *= price[i];
return product;
}
void factor(mega n, mega *factors, int *nfactors) /* By trial division */
{
mega i;
for (i = 2; i * i <= n; i = i == 2? 3 : i + 2)
for (; i * (n / i) == n; n /= i)
factors[(*nfactors)++] = i;
if (n > 1) factors[(*nfactors)++] = n;
}
int compare(mega *a, mega *b)
{
return *a - *b;
}