Prime Note

Number Theory Level 3

In Prime Country, "Prime Note" is used. The value of each Prime Note is the cube of any prime number. (For example, 8 Prime Dollar and 343 Prime Dollars are valid Prime Notes, as they can be expressed as $2^{3}$ and $7^{3}$ respectively)

A special law is designed in Prime Country, where the residents can only own limited types of Prime Note, based on their respective age levels, as stated below:

For 0- to 9-year-old, they can own Prime Note with the value of "Cube of the smallest prime number, only"
For 10- to 19-year-old, they can own Prime Note with the value of "Cube of the smallest prime number, and cube of the second smallest prime number"
For 20- to 29-year-old, they can own Prime Note with the value of "Cube of the smallest prime number, cube of the second smallest prime number, and cube of the third smallest prime number"
And so on.

In Prime Country, no change will be given for those who pay more.

Mr Ong is 19 years old in the year 2020. One day, Mr Ong is standing a treat with his friend in a Doughnut Shop. Mr Ong will order before his friend. Without knowing the number of doughnuts his friend wants to order, what is the minimum number of doughnuts that Mr Ong must order, so that no matter how many doughnuts that his friend orders, Mr Ong can still pay in the exact amount of money with the Prime Notes he owns?

Note that Mr Ong's friend can order any number of doughnuts, including 0 if he has no appetite.

The answer is 182.

1 solution

Ong Zhi Zhung
Sep 7, 2020

Mr Ong can own 2 different values of Prime Notes, namely

8 Prime Dollars ( $2^{3}$ , the cube of the smallest prime number), and
27 Prime Dollars ( $3^{3}$ , the cube of the second smallest prime number)

First, we can find for the largest integer dollars N, such that no combination of the Prime Notes (the 8 and 27 Prime Notes) is worth exactly N Prime Dollars. Or, more commonly known as the Frobenius Number .

By applying the formula of Frobenius Number, If a and b are relatively prime, then $N = g(a,b) = ab - a - b$

In this case, $N = g(8,27) = 8 \times 27 - 8 - 27 = 181$

Any number of doughnuts larger than 181 can be bought by Mr Ong with his Prime Notes. In the worst-case scenario, Mr Ong's friend has no appetite and he does not order any doughnut.

If Mr Ong orders 181 doughnuts, his friend order 0 doughnut, the total number of doughnuts will be $181+0=181$ , which is the largest integer that cannot be expressed as any combination of 8 and 27. Therefore, any integer greater than 181 can be expressed as a combination of 8 and 27.

The minimum number of doughnuts that Mr Ong must order = $181 + 1 = \boxed{182}$

Prime Note

The answer is 182.

1 solution

0 pending reports