Snake Arithmetic

laz0r · Post by **laz0r** » Tue Apr 13, 2010 8:16 pm

Am I being really stupid, or isn't the calculation of any D(n) just going to go on forever as we have a recursive function without a base case?

CodeX · Post by **CodeX** » Tue Apr 13, 2010 8:39 pm

Both functions have a conditional return based on a ternary operation, if n is any of None, False or 0 then it returns 1 as its not a bitwise operation.

laz0r · Post by **laz0r** » Wed Apr 14, 2010 3:41 pm

Ah, thanks!

laz0r · Post by **laz0r** » Wed Apr 14, 2010 4:31 pm

I've made a function that seems to model the snake one very closely, but it doesn't work - does Python overflow at a low value or something?

CodeX · Post by **CodeX** » Wed Apr 14, 2010 6:29 pm

Just to let you know D(10^12) is so large alone it would take 9.53219GiB just to hold it's value so you aren't going to find directly imitating the function the way to go (it will take 4x more to hold the stated value of 4*b). Time to break it into maths?

laz0r · Post by **laz0r** » Wed Apr 14, 2010 8:05 pm

I did break D(n) into maths, and I found a function that seems to generate N(b*4)b/D(b*4). My function holds (plus or minus 1) for b = 1 to 300. I've tried a range of values around my value; it is 13 digits long like it should be.
Nice to see you using the GiB! It's much underrated in my opinion.

arthur · Post by **arthur** » Sun Aug 08, 2010 5:16 am

Some calculus may help.

ShadowWidow · Post by **ShadowWidow** » Thu Dec 16, 2010 4:36 pm

I think i am at a position where i need some help.
I've transformed the recursive functions in to a iterativ one.
The first 250 values are exactly the same as in the original.
But the result i get for 1000000000000 is wrong.

My Number is 13 digits long and looks like 37...99.
I allready tried it in a range from -15 to +15 but they are all incorrect.

Can somebady give me a little hint ?

hxhl95 · Post by **hxhl95** » Sun Feb 27, 2011 1:15 am

same issue here, transformed the recursion into a simple almost linear function, got a value (the same value as poster above), doesn't work.

i've even simplified the thing by hand, it gives me exactly what i observe from calculating small values of b (b<1000).

hint?

uws8505 · Post by **uws8505** » Sun Feb 27, 2011 5:59 am

If you got an iterative solution, then look really closely at it.

An infinite series approximates to a finite series, and vice versa

moose · Post by **moose** » Sun Jul 17, 2011 12:05 pm

The serie is not in oesis.org

I transformed D(n) and N(n) to iterative functions. But it seems to take to long:

Code: Select all

$ time python snake-arithmetik.py -b    10 #time: 0m0.040s
$ time python snake-arithmetik.py -b   100 #time: 0m0.068s
$ time python snake-arithmetik.py -b  1000 #time: 0m14.037s
$ time python snake-arithmetik.py -b 10000 #time: 10h 5min 27s ... wow

How long did it take to calculate the result for b=1000000000000 (10*12 oder 10**12 in python

)?

uws8505 · Post by **uws8505** » Sun Jul 17, 2011 4:14 pm

No, that's not a series of natural numbers, it's a famous series of fractions.
Aware that the word "series" means the sum of numbers in a sequence

moose · Post by **moose** » Sun Jul 17, 2011 9:17 pm

uws8505 wrote:No, that's not a series of natural numbers, it's a famous series of fractions.
Aware that the word "series" means the sum of numbers in a sequence

Hrmpf ... I forgot how Python is handling integer division...

uws8505 · Post by **uws8505** » Sun Jul 17, 2011 10:15 pm

I just found out that the words above might be misleading...
I meant that there is a pattern in N(4*n) / D(4*n), not N(n) and D(n) individually, that you can approximate into an infinite series, and the precision increases with n so you don't need to worry about integer division.

aurora · Post by **aurora** » Thu Mar 01, 2012 9:27 am

mmm ... i figured out, what N and D are doing. the problem is, that even with an iterative algorithm calculation will take too long for 1000000000000. i wonder, if there is a math trick (again) or if i will get a correct result by using an approximate algorithm?