Как найти миллионное число в серии: 2 3 4 6 9 13 19 28 42 63 ...?

Question

Требуется около минуты, чтобы набрать 3000 в моем компе, но мне нужно знать миллионное число в серии. Определение является рекурсивным, поэтому я не вижу никаких ярлыков, кроме как вычислить все до миллионного числа. Как быстро рассчитать миллионное число в серии?

Серия Def

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

Интересно, что только один сайт перечисляет серию по версии Google: этот .

Слишком медленный код Bash

#!/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

Answer 1

Вы можете легко решить эту проблему, подумав о проблеме в двоичном виде. Этаж (3/2 * i) в основном сдвиг вправо, обрезать и добавить. В псевдокоде:

0b_n[0]   = 10              // the start is 2
0b_n[1]   = 10 + 1(0) = 11  // shift right, chop one bit off and add 
0b_n[i+1] = 0b_n[i] + Truncate(ShiftRight(0b_n[i]))

Это должно быть достаточно быстро реализовано в любой форме.

Я только что реализовал это в Mathematica, и кажется, что операция BitShiftRight также отсекает бит после позиции устройства, так что об этом позаботятся автоматически. Вот один лайнер:

In[1] := Timing[num = Nest[(BitShiftRight[#] + #) &, 2, 999999];]
Out[2] = {16.6022, Null}

16 секунд, число печатается просто отлично, хотя оно довольно длинное:

In[2] := IntegerLength[num]
Out[2] = 176092

In[3] := num
Out[3] = 1963756...123087

Полный результат здесь .

Answer 2

Вы почти нашли это.В следующий раз, посмотрите Онлайн-энциклопедию целочисленных рядов .

Вот запись: http://oeis.org/A061418

     FORMULA    

a(n) = ceiling[K*(3/2)^n] where K=1.08151366859...

The constant K is 2/3*K(3) (see A083286). - Ralf Stephan, May 29, 2003 

Сказано:

>>> def f(n):
...     K = 1.08151366859
...     return int(ceil(K*(1.5)**n))

Тест на вменяемость:

>>> for x in range(1, 10):
...     print f(x)
...     
2
3
4
6
9
13
19
28
42

Отлично!А как насчет 1000000:

>>> f(1000000)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
  File "<input>", line 3, in f
OverflowError: (34, 'Result too large')

Ну, я попробовал.:] Но вы поняли.

Отредактируйте еще раз: Решение найдено!См. Тимо или Лассе В. Карлсена . Ответы

Редактировать: Использование идеи Тимо:

выход

1963756763 ... 226123087 (176092 цифры)

% time test.py > test.out

real    0m21.735s
user    0m21.709s
sys 0m0.024s

Answer 3

Причина, по которой ваш скрипт такой медленный, заключается в том, что он порождает bc три раза, tr один раз и sed один раз в цикле.

Перепишите все это в bc и сделайте sed в конце. Мой тест показывает, что bc -только версия работает в 600 раз быстрее. На старой медленной системе для версии bc потребовалось чуть меньше 16 минут, чтобы найти 100-тысячное значение (только печатая последнее).

Кроме того, обратите внимание, что ваша функция "floor" на самом деле "int".

#!/usr/bin/bc -lq
define int(n) {
    auto oscale
    oscale = scale
    scale = 0
    n = n/1
    scale = oscale
    return n
}

define series(n) {
    return int(3/2*n)
}

n = 2
end = 1000
for (count = 1; count < end; count++ ) {
    n = series(n)
}
print count, "\t", n, "\n"
quit

Обратите внимание, что print является расширением, и некоторые версии bc могут не иметь его. Если это так, просто обратитесь к переменной, и ее значение должно быть выведено.

Теперь вы можете сделать chmod +x series.bc и назвать его так:

./series.bc | tr -d '\n' | sed 's.\\..g'

Answer 4

Я использовал следующую программу Java:

import java.math.*;

public class Series {
    public static void main(String[] args) {
        BigInteger num = BigInteger.valueOf(2);
        final int N = 1000000;

        long t = System.currentTimeMillis();
        for (int i = 1; i < N; i++) {
            num = num.shiftLeft(1).add(num).shiftRight(1);
        }
        System.out.println(System.currentTimeMillis() - t);
        System.out.println(num);
    }
}

Вывод обрезан: ( полный вывод на пастбине )

516380 (milliseconds)
196375676351034182442....29226123087

Так что на моей скромной машине прошло около 8,5 минут. Я использовал -Xmx128M, но не уверен, действительно ли это было необходимо.

Возможно, есть лучшие алгоритмы, но это заняло 10 минут, включая написание простой реализации и запуск программы.

Образцы прогонов

• N=500 (согласен с OEIS 061418 )
• N=100K (1445232038814....522773508)

Answer 5

Вот версия Python, которая на моем 10-летнем ноутбуке занимает около 220 секунд:

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

Он выдает тот же результат, что и этот ответ на пастбине (то есть я проверил его начало и конец, но не все).

Answer 6

Хм, bash - это не то, что я использовал бы для высокоскоростной числовой обработки. Получите себе копию GMP и соберите для этого C-программу.

Может быть, есть математическая формула, чтобы дать ее вам быстро, но, если вам понадобится время, чтобы понять это, GMP, вероятно, может дать вам результат: -)

Answer 7

Это очень легко сделать в Пари :

n=2;for(k=1,10^6,n+=n>>1)

Это займет 14 секунд на моей машине. Конечно, есть более быстрые способы - GMP приходит на ум - но зачем? Вы не сможете сократить время выполнения более чем на 10 секунд, а время разработки будет составлять порядка минут . :)

Незначительная точка: в исходной формулировке неоднозначно, желателен ли миллионный член n ₉₉₉₉₉₉ или n _1000000 , число с индексом один миллион; Я даю последнее, так как вижу, что первое уже рассчитано выше.

Answer 8

Возможно, вы сможете немного приблизиться, используя более подходящий язык, например, Схема:

(define (series n) (if (= n 0) 2
                       (quotient (* 3 (series (- n 1))) 2)))

Это вычисляет 17610 цифр (series 100000) примерно за 8 секунд на моей машине. К сожалению, (series 1000000) все еще занимает слишком много времени, чтобы даже у более новой и более быстрой машины появилась надежда закончить через минуту.

Переключение на C ++ с большой целочисленной библиотекой (в данном случае NTL):

#include <NTL/zz.h>
#include <fstream>
#include <time.h>
#include <iostream>

int main(int argc, char **argv) {
    NTL::ZZ sum;

    clock_t start = clock();
    for (int i=0; i<1000000; i++) 
        sum = (sum*3)/2;
    clock_t finish = clock();
    std::cout << "computation took: " << double(finish-start)/CLOCKS_PER_SEC << " seconds.\n";

    std::ofstream out("series_out.txt");
    out << sum;

    return 0;
}

Это вычисляет серию для 1000000 за 4 минуты 35 секунд на моей машине. Это достаточно быстро, чтобы я мог почти поверить, что действительно быстрая новая машина может хотя бы приблизиться к завершению за минуту (и да, я проверил, что произошло, когда я использовал смены вместо умножения / деления - это был медленнее).

К сожалению, вычисления в замкнутой форме, предложенные другими, похоже, мало помогают. Чтобы использовать его, вам нужно вычислить постоянную K с достаточной точностью. Я не вижу вычисления K в замкнутой форме, так что на самом деле это просто сдвигает итерацию к вычислению K, и похоже, что вычисление K с достаточной точностью немного (если вообще имеет место) быстрее, чем вычисление исходного ряда.

Answer 9

Это идентифицируется как последовательность A061418 на сайте sequences (AKA "Онлайн-энциклопедия целочисленных последовательностей"); за соответствующую страницу ,

ФОРМУЛА a(n) =A061419(n)+1 = ceiling[K*(3/2)^n], где K=1.08151366859 ... Постоянная K равна 2/3*K(3) (см. A083286).

и с подходящей высокоточной библиотекой (GMP, как уже предлагалось, или MPIR, и, возможно, оберткой сверху, как мой ребенок gmpy для Python), вы можете использовать формулу закрытой формы для более быстрое вычисление «миллионного элемента в серии» и т. п.

Часто можно поместить рекурсивно определенные рекурсии в замкнутые формулы. Для обширного введения новичка в предмет, Конкретная математика (Грэм, Кнут и Паташник) действительно трудно победить.

Answer 10

Это почти повторение первого порядка, за исключением пола, который запутывает вещи. Если вам не нужен пол,

http://en.wikipedia.org/wiki/Recurrence_relation

Также не используйте bash.