Pibonacci numbers

[Xantipius]

You might have heard of the Fibonacci numbers and of the number pi.
If you let these two ideas merge, a new and esoteric concept comes into being:
the Pibonacci numbers. These can be defined for real x >= 0 by:

P(x) = 1 for 0 <= x < 4
P(x) = P(x - 1) + P(x - pi) for x >= 4,

where pi = 3.1415926535... In this problem, you are asked to compute P(x) for a given x,
where x is a non-negative integer number (less than 30000).

Hints:

P(0) = 1

P(4) = 2

P(10) = 14

P(11) = 20

P(100) = 5338198515572716

P(10000) =
30545061766548826347723622438005598334547039374992
90113008199964715857981506903607585689770339053086
23582036970173222028695034160773457277489005548434
17020796291845338949687167603974595558347137121217
94967248559855843389551994870458311313312344050309
26953096233856792547217501033692773439422753706749
75787164384879377786735733077303986883046271278570
21201893525701528659063857187966332441184716237226
69326907300731819842942377628687148684970555383475
59934470505111156957972054431125340438368447868289
62291699146142605916313354358025513818642587234401
29221003159635553765229982268111989465247965530579
11455875848567970805369891745228832920941822856078
71837646059510451089216388517941864454024561344107
87338437660695880294107196594263246220666104829574
17308001324200284988508657339845510890573271727796
85014714292928424032536221127315507955108814140393
81098371314381088699431874240026717000932753775313
09851253295038144278739276090483044831966040316689
77605611576202999395210908046726682599785866106081
25086280732687524214522573222031212086354074164955
96961873718206154505873516193044667895322796150306
05267341100116655225123834641245441248980916942413
26205649996121608255109099308055932633784720918028
64438756163075739226587263206887350265551536945610
37013044605514190168453868193943302408320903816087
56718108514024423395755370256937230041005874987898
52381791671318491462930261787039199555019880263789
23751491521989840810768222435642807253020761248276
33075558810802435250802095650410899109886849531218
27273903819599408284858157102491364090281856443316
14100508402747147674473055900552596251489724880320
7988426623314191

P(29999) = ???

P.S.
It's a problem from IPSC 2001.

[Dani]

Is this just a homework problem? What is IPSC 2001???

[pritaeas]

http://ipsc.ksp.sk/

[np complete]

@ Xantipius

Have you tried solving it mathematically ? By solving the recurrsion.

[Xantipius]

@np complete, do you mean smth like this:?

from math import pi

def pib(x):
    if x < 4:
        return 1
    return pib(x - 1) + pib(x - pi)

Obviously, it's not the solution.

[Xantipius]

If it'd be "regular" Fibonaccies, then it could be solved like this (by matrix multiplication):

def mx_power(a, n):
    def mx_mult(x, y):
        xy = [[0, 0], [0, 0]]
        xy[0][0] = x[0][0] * y[0][0] + x[0][1] * y[1][0]
        xy[0][1] = x[0][0] * y[0][1] + x[0][1] * y[1][1]
        xy[1][0] = x[1][0] * y[0][0] + x[1][1] * y[1][0]
        xy[1][1] = x[1][0] * y[0][1] + x[1][1] * y[1][1]
        return xy
    if n == 1:
        return a
    z = mx_power(a, n / 2)
    z = mx_mult(z, z)
    if n % 2 == 1:
        z = mx_mult(z, a)
    return z

a = [[0, 1], [1, 1]]

while 1:
    n = input('Fib #')
    b = mx_power(a, n)
    print b[0][1]

#####################################

Fib #1
1
Fib #2
1
Fib #3
2
Fib #4
3
Fib #5
5
Fib #6
8
Fib #7
13
Fib #333
1751455877444438095408940282208383549115781784912085789506677971125378
Fib #8838
48225809596142534376618515362027218452508426090074012557355634337847915612490223
18120365804305785581728479437697584525555564681211807799338004105533110761575522
96912560126893691740944915344256753117339760354416396594599180516587355753095490
30521474122558244060501148290159145334419074812775281240826894686945130920468766
11860207946005245829996752193087718016554989764096033854492846895243426943369212
21607820048120418520658545388789707380991628975932820237612906232856026138749321
26237780464892932617189488990614045548635208017100860651236068662537861490334043
44215159543263717182033994043486344602183493422622175520597873907158095570271080
95807709501340633203297325399977270630853294000731555630763323404978288332480189
65025748421768900286160792796561391956151937138165763730339386988180202672907051
57985780707285937004403532029349585638112580101535912624388057075177682945808659
81360956877549852415522747638224382957964154889014243726132784119623176484637349
60828256910997881694731274476476851075393192067342121769023839107117511426357830
90279866103231589984391898195080766781699569058594395050266523708581378365859557
03972571910543034240945771710369801129775967832767478314090654259264133871607249
93852643809660060157460531130424300577332148267883719780553544298706240142373827
00477752579369462684994079842774010795711145302897441995790312827146255645251118
62872177420547092043358047694093167874308893781212787664498331046020847324996723
57096673203695685612674682736318028233540880071923506401998213016828869643542327
01398407242537450238944533389061086886440948089440536201156377467752427032611488
69588620631539427050286368171172119714590518649581262001071022674956700818149009
76368402184279431235914229382452571080387286649317153626553282428353728897494159
76298295100354976592706081718672786556808152975580383891140547171664608953919839
5239944
Fib #

[np complete]

No, I meant, by mathematically solving it using pencil paper. For example I found last night that there may be a sequence in p(i) - p(i - 1). I got something like this 1,1,1,2,3,4,...

I tried solving by using discrete math. See this. But I'm stuck with a equation which has degree pi = 3.1415926535, that is irrational degree. I will now try solve this equation by numerical methods ( basically approximating ).

[DavidB]

I am curious: besides being an interesting programming exercise, do these numbers have any practical applications? From what applications or situations do these numbers arise?

[Xantipius]

@DavidB, I strongly doubt it has any practical use.

@all, you can test your solutions here => http://www.spoj.pl/problems/PIB
My account there => http://www.spoj.pl/users/zzz but seems I had quitted the game.