Как делают я нахожу миллионное число в ряду: 2 3 4 6 9 13 19 28 42 63 …?

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

Вот запись: 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')

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

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

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

import gmpy
n=gmpy.mpz(2)
for _ in xrange(10**6-1):
    n+=n>>1
print(n)

дает

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

% time test.py > test.out

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

Я использовал следующую 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);
    }
}

Обрезанный вывод: ( полный вывод на pastebin )

516380 (milliseconds)
196375676351034182442....29226123087

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

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

Пробные прогоны

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

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

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

Кроме того, не используйте bash.

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

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

Также обратите внимание, что ваша функция «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'

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

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

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

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

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

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

Вот версия на 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));

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

Рекурсивная формулировка займет довольно много времени при большинстве Curcumstances, потому что он должен поддерживать стек машины. Почему бы не использовать динамический программирование вместо этого?

т.е. (псевдокод)

bignum x = 2
for (int i = 1; i < 1000000; i++) {
    x = floor(3.0/2*x)
}

Конечно, для значимого результата вам понадобится высокоточная числовая библиотека.

Я преобразовал идеи Тимо в elisp. Ошибка 100, что дает отрицательное число. FAIL, см. 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

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

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

Это вычисляет 17610 цифр (серия 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 с достаточной точностью немного (если таковое имеется) быстрее, чем вычисление исходной серии.

Это очень просто сделать в Pari :

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

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

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