umgeher's changelog

Work­ing from left-to-right if no digit is exceeded by the digit to its left it is called an increas­ing num­ber; for exam­ple, 134468.

Sim­i­larly if no digit is exceeded by the digit to its right it is called a decreas­ing num­ber; for exam­ple, 66420.

We shall call a pos­i­tive inte­ger that is nei­ther increas­ing nor decreas­ing a “bouncy” num­ber; for exam­ple, 155349.

Clearly there can­not be any bouncy num­bers below one-hundred, but just over half of the num­bers below one-thousand (525) are bouncy. In fact, the least num­ber for which the pro­por­tion of bouncy num­bers first reaches 50% is 538.

Sur­pris­ingly, bouncy num­bers become more and more com­mon and by the time we reach 21780 the pro­por­tion of bouncy num­bers is equal to 90%.

Find the least num­ber for which the pro­por­tion of bouncy num­bers is exactly 99%.

#!/usr/bin/env python

def calc(x):
    a = d = False
    x = str(x)

    for y in range(len(x)-1):
        if x[y+1] > x[y]:
            a = True
        elif x[y+1] < x[y]:
            d = True

        if a and d:
            return True

    return False

x = 21780
p = 0.90
b = x * p

while p != 0.99:
    x+= 1 

    if calc(x):
        b+= 1

    p = float(b)/x

print x

/home/umgeher/war/hg/euler/python> time python 112.py
1587000

Time spent in user mode   (CPU seconds) : 5.449s
Time spent in kernel mode (CPU seconds) : 0.007s
Total time                              : 0:05.46s
CPU utilisation (percentage)            : 99.6%
Times the process was swapped           : 0
Times of major page faults              : 0
Times of minor page faults              : 649
/home/umgeher/war/hg/euler/python>