How do I find the millionth number in the series: 2 3 4 6 9 13 19 28 42 63 ...?

Asked 2010-05-15T15:11:40.127

It takes about minute to achieve 3000 in my comp but I need to know the millionth number in the series. The definition is recursive so I cannot see any shortcuts except to calculate everything before the millionth number. How can you fast calculate millionth number in the series?

Series Def

n_{i+1} = \floor{ 3/2 * n_{i} } and n_{0}=2.

Interestingly, only one site list the series according to Google: this one.

Too slow Bash code

#!/bin/bash

function series 
{
        n=$( echo "3/2*$n" | bc -l | tr '\n' ' ' | sed -e 's@\\@@g' -e 's@ @@g' );
                                        # bc gives \ at very large numbers, sed-tr for it
        n=$( echo $n/1 | bc )           #DUMMY FLOOR func
}

n=2
nth=1

while [ true ]; #$nth -lt 500 ];
do
        series $n                        # n gets new value in the function through global value
        echo $nth $n
        nth=$( echo $nth + 1 | bc )     #n++
done

Edit Report

2 Answers

Here's a Python version that on my 10-year old laptop takes about 220 seconds to run:

import math;
import timeit;

def code():
  n = 2
  nth = 1

  while nth < 1000000:
    n = (n * 3) >> 1
    nth = nth + 1

  print(n);

t = timeit.Timer(setup="from __main__ import code", stmt="code()");
print(t.timeit(1));

It produces the same result that this answer has on the pastebin (that is, I verified the start and end of it, not everything.)

answered 2010-05-15T19:17:04.223

I converted Timo's ideas to elisp. It fails with 100, giving negative number. FAIL, please, see no BigNums!

(progn
  (let ((a 2)
        (dummy 0))
    (while (< dummy 100)
      (setq a (+ a (lsh a -1)))
      (setq dummy (1+ dummy)))
    (message "%d" a)))
-211190189 #WRONG evalution

answered 2010-05-16T17:41:41.060

How do I find the millionth number in the series: 2 3 4 6 9 13 19 28 42 63 ...?

2 Answers

Your Answer