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

Ответ 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

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

Ответ 2

Ты почти нашел это. В следующий раз ознакомьтесь с Online Encyclopedia of Integer Series.

Здесь запись: 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

Awesome! Теперь как насчет 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')

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

Изменить снова: Решение найдено! См. Timo или Lasse V. Karlsen.

Изменить: Использование идеи битового смещения Timo:

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

Ответ 3

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

Перепишите все это в bc и выполните sed в конце. Мой тест показывает, что версия bc -only более чем в 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'

Ответ 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);
    }
}

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

516380 (milliseconds)
196375676351034182442....29226123087

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

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

Примеры прогона

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

Ответ 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));

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

Ответ 6

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

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

Ответ 7

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

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

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

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

Ответ 8

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

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

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

Переключение на С++ с большой целой библиотекой (в этом случае 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 до достаточной точности мало (если оно есть) быстрее, чем вычисление исходной серии.

Ответ 9

Это очень легко сделать в Pari:

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

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

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

Ответ 10

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

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

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

Ответ 11

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

то есть. (Псевдокод)

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

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

Ответ 12

Я превратил идеи Тимо в 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