numbers

There are 2 posts tagged numbers (this is page 1 of 1).

SPOJ: 1030. Triple Fat Ladies

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.

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

Which gets us:

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: 192 + 250(k-1)

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
4
6
9
11
14
16

If you do some basic arithmetics you see that:

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

 

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()))

SPOJ: 3442. The last digit

Nestor was doing the work of his math class about three days but he is tired of make operations a lot and he should deliver his task tomorrow. His math’s teacher gives two numbers a and b. The problem consist in find the last digit of the potency of base a and index b. Help Nestor with his problem. You are given two integer numbers: the base a (0 <= a <= 20) and the index b (0 <= b <= 2,147,483,000). You have to find the last digit of a^b.

Problem: Sphere Online Judge (SPOJ) – Problem LASTDIG

Solution: I don’t really have an background in number theory, so I decided to approach this problem empirically. My main source of information was this small Python program:

for i in xrange(1, 20):
    print i, str(base ** i)[-1:]

I checked the last digit for each base (0..20) and looked for patterns. Happily, I found them. Here’s a snippet:

x > 0

0 ^ x => 1
1 ^ x => 1
2 ^ x => 2^1 -> 2
         2^2 -> 4
         2^3 -> 8
         2^4 -> 6

3 ^ x => 3^1 -> 3
         3^2 -> 9
         3^3 -> 7
         3^4 -> 1

4 ^ x => 4^1 -> 4
         4^2 -> 6

5 ^ x => 5

The rest is straight forward and thanks to the 700B source code size limitations, the source code is pretty unreadable. ;)