In article <voevo3$1m9hs$1@dont-email.me>,
David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> wrote:

Not having worked through it yet, I'm now simply
surprised, rather than disbelieving, that you can converge on any integer,
no matter what size, with a fixed number of coins.

I think you must have misunderstood:

(2) Any positive integer amount can be made. This will require an
unlimited number of coins in total, but not more than 14 of any
single value.

You can use up to 14 coins of each denomination.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vobinl$1jvp$1@macpro.inf.ed.ac.uk>,
Richard Tobin <richard@cogsci.ed.ac.uk> wrote:

In article <vo9t64$hlp5$2@dont-email.me>,
David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> wrote:

Please don't post a direct answer to the question posed, but I'd welcome a >>bit of guidance on Mathsbombe question 3.

I have guessed the correct answer without understanding the problem.

I have now understood the problem (and its solution).

Let me clarify the points that have caused some doubt about the
problem itself.

(1) The coins have value x^0 (=1), x^1 (=x), x^2, x^3, ... for some
irrational x > 3.3.

(2) Any positive integer amount can be made. This will require an
unlimited number of coins in total, but not more than 14 of any
single value.

Here are some obvious observations:

(1) We could equally well consider the problem to be representing an
integer in the irrational base x, where the digits are 0 .. 14.

(2) We need to find an irrational x such that we can add multiples of
its powers to get integers. That rules out x being transcendental
by definition.

And finally a hint that should not give much away until you are on the
right track:

You may, like me, stumble upon the correct value of x and then see
that it works for numbers up to N - a number greater than 400 - but
not immediately see how it works beyond that. I had to think of it
somewhat differently to see that it does.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 10 Feb 2025 15:38:08 +0000 (UTC), Richard Tobin wrote:

I have now understood the problem (and its solution).

Thanks for the clarification on the question and guidance on how to
approach a solution. Not having worked through it yet, I'm now simply surprised, rather than disbelieving, that you can converge on any integer,
no matter what size, with a fixed number of coins. It's working on things
that are surprising that are most rewarding. I'll get on it.

--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 11 Feb 2025 11:11:56 +0000 (UTC), Richard Tobin wrote:

I think you must have misunderstood:

(2) Any positive integer amount can be made. This will require an
unlimited number of coins in total, but not more than 14 of any
single value.

You can use up to 14 coins of each denomination.

You are quite right, I had misunderstood. My level of surprise is even
more diminished.

Thanks,
--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Tue, 11 Feb 2025 19:28:57 -0000 (UTC), David Entwistle wrote:

You are quite right, I had misunderstood. My level of surprise is even
more diminished.

Congratulations, this is the correct answer!

Thanks for all the comments and guidance. I have now stumbled on the
answer reported as correct. I can't say I'm all that happy with it, but it gives me a starting point to look a little deeper and see if I can
increase my contentment.

Best wishes,
--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Mon, 10 Feb 2025 15:38:08 +0000 (UTC), Richard Tobin wrote:

You may, like me, stumble upon the correct value of x and then see that
it works for numbers up to N - a number greater than 400 - but not immediately see how it works beyond that. I had to think of it somewhat differently to see that it does.

Yes... That's where I'm at at the moment.

I'll try and think differently... :o)

--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Thu, 20 Feb 2025 08:48:47 -0000 (UTC), David Entwistle wrote:

I'll try and think differently... :o)

I wouldn't have guessed, nor predicted the sequence of numbers of coins of
each denomination required to match the desired increasing monetary value.

221 matched by 221.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 11 * x^0
222 matched by 222.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 12 * x^0
223 matched by 223.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 13 * x^0
224 matched by 224.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 14 * x^0
225 matched by 225.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 0 * x^0
226 matched by 226.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 1 * x^0
227 matched by 227.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 2 * x^0
228 matched by 228.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 3 * x^0
229 matched by 229.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 4 * x^0
230 matched by 230.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 5 * x^0

Does anyone have an easy explanation why steps are jumped in the sequence
of additional coins, or is it a mistake on my part?

--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <vp7dvm$2s8nd$1@dont-email.me>,
David Entwistle <qnivq.ragjvfgyr@ogvagrearg.pbz> wrote:

221 matched by 221.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 11 * x^0
222 matched by 222.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 12 * x^0
223 matched by 223.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 13 * x^0
224 matched by 224.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 14 * x^0

So you have correctly chosen x such that x^2 + x = 15. Up to here we
are working in base 15 with the x^0 coins (obviously) acting as the
units column, and pairs of x^1 and x^2 coins acting as the 15s column.

To continue in base 15 beyond 224 we need a column for 15^2. Since
x^2 + x is 15, (x^2 + x)^2 is 15^2, and is equal to x^4 + 2x^3 + x^2.
So you can get 225 by using a set of one x^4, two x^3, and one x^2
coin.

225 matched by 225.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 0 * x^0
226 matched by 226.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 1 * x^0
227 matched by 227.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 2 * x^0
228 matched by 228.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 3 * x^0
229 matched by 229.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 4 * x^0
230 matched by 230.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 5 * x^0

As you have presumably noticed, this works for a while, but will run
into a problem when you get to 435 = 15^2 + 14*15 which would be

1*x^4 + 2*x^3 + 15*x^2 + 14*x^1

because now you have more than 14 of one coin.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Thu, 20 Feb 2025 15:04:52 +0000 (UTC), Richard Tobin wrote:

As you have presumably noticed, this works for a while, but will run
into a problem when you get to 435 = 15^2 + 14*15 which would be

1*x^4 + 2*x^3 + 15*x^2 + 14*x^1

because now you have more than 14 of one coin.

433 matched by 433.00, 1 * x^4 + 2 * x^3 + 14 * x^2 + 13 * x^1 + 13 * x^0
434 matched by 434.00, 1 * x^4 + 2 * x^3 + 14 * x^2 + 13 * x^1 + 14 * x^0
435 matched by 435.00, 2 * x^4 + 3 * x^3 + 0 * x^2 + 14 * x^1 + 0 * x^0
436 matched by 436.00, 2 * x^4 + 3 * x^3 + 0 * x^2 + 14 * x^1 + 1 * x^0

Thanks for the explanation. I have to admit to being slightly amazed that anyone can not only understand, but also clearly describe, what is going
on.

Personally, I'm very happy to have gone from not understanding the
question at all to fully grasping the the question, arriving at a solution
and almost fully-understanding that solution. I'll work on the last bit.

Thanks to all for the support. Onwards and upwards...

--
David Entwistle

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 20/02/2025 14:24, David Entwistle wrote:

On Thu, 20 Feb 2025 08:48:47 -0000 (UTC), David Entwistle wrote:

I'll try and think differently... :o)

I wouldn't have guessed, nor predicted the sequence of numbers of coins of each denomination required to match the desired increasing monetary value.

221 matched by 221.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 11 * x^0
222 matched by 222.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 12 * x^0
223 matched by 223.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 13 * x^0
224 matched by 224.00, 0 * x^4 + 0 * x^3 + 14 * x^2 + 14 * x^1 + 14 * x^0
225 matched by 225.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 0 * x^0
226 matched by 226.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 1 * x^0
227 matched by 227.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 2 * x^0
228 matched by 228.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 3 * x^0
229 matched by 229.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 4 * x^0
230 matched by 230.00, 1 * x^4 + 2 * x^3 + 1 * x^2 + 0 * x^1 + 5 * x^0

Does anyone have an easy explanation why steps are jumped in the sequence
of additional coins, or is it a mistake on my part?

tldr; it's because of the base-15 nature of the solution. Put another way it's because of the
"casting out 15s" process explained below, which naturally has jumps in behaviour when going over
powers of 15...

-----------------------
Longish (due to worked example), but easy to follow explanation for why the solution works...

I could ask what is your x. Tobin has assumed you have it correctly as the positive solution for

x^2 + x = 15 [1].

Now we can use this to convert any number like say 8241 (chosen at random) into a set of coins using
no more than 14 of each denomination. Effectively we're looking for a polynomial in x, using only
integer coefficients 0 to 14. The power of x^n in the polynomial represents the coins of
denomination x^n.

The secret of this is that we start by ignoring the "max 14 coins of any denomination" restriction,
and then make a succession of substitutions to "cast out" multiples of 15 as they occur, using [1].

So....
8241 = 561*15 + 6 = 561*(x^2 + x) + 6
= 561x^2 + 561x + 6

...ok, so far we have the final 6 [= 6x^0], which is less than 15, and some polynomial with terms of
order x^1 and higher. We can use 6 coins of denomination 1, but we're not allowed 561 coins of
denomination x because 561 > 15. So we continue "casting out 15s". Note that all the steps that
follow do not affect the "resolved" term 6x^0 on the right of the above equations...

= 561x^2 + (37*15 + 6)x + 6
= 561x^2 + (37*(x^2 + x) + 6)x + 6
= 561x^2 + 37x^3 + 37x^2 + 6x + 6
= 37x^3 + 598x^2 + 6x + 6

...ok now we've sorted the x^1 term as 6x^1, and 6<15 and we can move on to the 598x^2 term, and so
on...

= 37x^3 + (39*15 + 13)x^2 + 6x + 6
= 37x^3 + (39*(x^2 + x) + 13)x^2 + 6x + 6
= 37x^3 + 39x^4 + 39x^3 + 13x^2 + 6x + 6
= 39x^4 + 76x^3 + 13x^2 + 6x + 6

...(x^2 term sorted, move on to 76x^3)...

= 39x^4 + (5*15 + 1)x^3 + 13x^2 + 6x + 6
= 39x^4 + (5*(x^2 + x) + 1)x^3 + 13x^2 + 6x + 6
= 39x^4 + 5x^5 + 5x^4 + 1x^3 + 13x^2 + 6x + 6
= 5x^5 + 44x^4 + 1x^3 + 13x^2 + 6x + 6
...
= 5x^5 + (2*15 + 14)x^4 + 1x^3 + 13x^2 + 6x + 6
= 5x^5 + (2*(x^2 + x) + 14)x^4 + 1x^3 + 13x^2 + 6x + 6
= 5x^5 + 2x^6 + 2x^5 + 14x^4 + 1x^3 + 13x^2 + 6x + 6
= 2x^6 + 7x^5 + 14x^4 + 1x^3 + 13x^2 + 6x + 6

...and we're done. If called upon to pay 8241, we can do so with
2 coins of denomination x^6,
and 7 coins of denomination x^5,
and 14 coins of denomination x^4,
and 1 coins of denomination x^3,
and 13 coins of denomination x^2,
and 6 coins of denomination x^1,
and 6 coins of denomination x^0,

The above process is tedious, and probably I've made a miscalculation somewhere, but it's just an
example to show that the "casting out 15s" approach works. Each step makes progress, sorting out
the next lowest unresolved coin denomination, and clearly the steps end at some point otherwise we
would be getting higher and higher powers of x cropping up. But x > 3.3 so x^n grows without bound
as n increases, so at some point a single x^n coin would exceed our starting amount to be paid,
which can't happen.

Note that the above process could be applied with any "similar" algebraic positive number x, with
obvious adjustments. E.g. if x satisfied

x^7 + 3x^4 + 17x^3 + 4x = 41

then we could pay any whole number amount using no more than 40 coins of any denomination, by
"casting out 41s".

So I suppose the maths bit of the puzzle is realising this (i.e. understanding the casting out
process or something equivalent) and the puzzly bit is working out which polynomial equation x must
satisfy given the constraints x > 3.3, no more than 14 coins etc.. (There's only one equation that
could conceivably work!)

Hope this helps,
Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <hbidnYrnI_7s7Cr6nZ2dnZfqnPadnZ2d@brightview.co.uk>,
Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:

[detailed description and worked example]

To reduce it to its minimum...

If
15 = x^2 + x
then
15x^n = x^(n+2) + x^(n+1)

so we can exchange 15 coins of any one denomination for one each of
the two next higher denominations.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 20/02/2025 20:41, Richard Tobin wrote:

In article <hbidnYrnI_7s7Cr6nZ2dnZfqnPadnZ2d@brightview.co.uk>,
Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:

[detailed description and worked example]

To reduce it to its minimum...

If
15 = x^2 + x
then
15x^n = x^(n+2) + x^(n+1)

so we can exchange 15 coins of any one denomination for one each of
the two next higher denominations.

-- Richard

Right - and we can keep repeating that as many times as required so that eventually all
denominations have less than 15 coins used. (That's effectively what happens in my example,
starting with 8241 unit coins.)

Mike.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)