Pattern Matchers have been designed for various sorts of patterns. Mr. HKP likes to observe patterns in numbers. After completing his extensive research on the squares of numbers, he has moved on to cubes. Now he wants to know all numbers whose cube ends in 888.

Given a number k, help Mr. HKP find the kth number (indexed from 1) whose cube ends in 888.

**Problem:** Sphere Online Judge (SPOJ) – Problem EIGHTS

**Solution:** Yeah, an other number problem! And again I just looked for patterns.

1 2 3 |
for i in xrange(0, 4444): if str(i**3)[-3:] == "888": print i, i**3 |

Which gets us:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
192 7077888 442 86350888 692 331373888 942 835896888 1192 1693669888 1442 2998442888 1692 4843965888 1942 7323988888 2192 10532261888 2442 14562534888 2692 19508557888 2942 25464080888 3192 32522853888 3442 40778626888 3692 50325149888 3942 61256172888 4192 73665445888 4442 87646718888 |

**EDIT:** Thanks to the anonymous person who found a simple connection between the numbers but can’t properly communicate. You can find the k-th number with this simple formula:

You should see that each number ends in 2. If you look closer you see that the last two digits are 42 if i is even, and 92 if i is odd. Let’s look at the other digits. We get:

1 2 3 4 5 6 7 |
1 4 6 9 11 14 16 |

If you do some basic arithmetics you see that:

1 2 3 4 5 6 7 |
1 4 = 1 + 3 6 = 4 + 2 9 = 6 + 3 11 = 9 + 2 14 = 11 + 3 16 = 14 + 2 |

You can calculate your first digits either recursively or search for a function. This takes probably some time, so I looked this sequence up. OEIS gives us the formular: a(n) = floor((5n-2)/2) for n > 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
from math import floor def kthnumber(k): if k > 2: num = "%i" % int((floor( (5 * (k - 1) + 3) / 2.0 ))) else: if k == 1: num = "1" elif k == 2: num = "4" if k % 2 == 0: num += "42" else: num += "92" return num t = int(raw_input()) for c in xrange(0, t): print kthnumber(int(raw_input())) |