¿Cómo encuentro el número millonésimo de la serie: 2 3 4 6 9 13 19 28 42 63 ...?

Casi lo encuentras. La próxima vez, echa un vistazo a la Enciclopedia en línea de Series Enteras.

Aquí está la entrada: 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 

Que decía:

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

Prueba de cordura:

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

Impresionante! Ahora qué tal 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')

Bueno, lo intenté. :] Pero entiendes la idea.

Editar de nuevo: Solución se encuentra! Ver Timo o Lasse V. Karlsen's respuestas.

Editar: Usando La idea de cambio de bits de Timo:

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

Rinde

1963756763...226123087 (176092 dígitos)

% time test.py > test.out

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

La razón por la que su script es tan lento es que está generando bc tres veces, tr una vez y sed una vez en un bucle.

Reescribe todo en bc y haz el sed al final. Mi prueba muestra que la versión de solo bc es más de 600 veces más rápida. Tomó poco menos de 16 minutos en un viejo sistema lento para que la versión bc encontrara el valor 100,000 (solo imprimiendo el último).

También, tenga en cuenta que su función "piso" es en realidad "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

Tenga en cuenta que print es una extensión y algunas versiones de bc pueden no tenerla. Si es así, solo haga referencia a la variable por sí misma y su valor debe ser de salida.

Ahora puedes hacer chmod +x series.bc y llamarlo así:

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

Usé el siguiente programa 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);
    }
}

La salida, recortada: (salida completa en pastebin)

516380 (milliseconds)
196375676351034182442....29226123087

Así que me tomó unos 8,5 minutos en mi modesta máquina. Usé -Xmx128M, pero no estoy seguro de si eso era realmente necesario.

Probablemente hay mejores algoritmos por ahí, pero esto tomó un total de 10 minutos, incluyendo escribir la implementación ingenua y ejecutar el programa.

Ejecuciones de muestra

• N=500 (está de acuerdo con OEIS 061418)
• N=100K (1445232038814....522773508)

Aquí hay una versión de Python que en mi computadora portátil de 10 años tarda unos 220 segundos en ejecutarse:

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

Produce el mismo resultado que esta respuesta tiene en el pastebin (es decir, he verificado el principio y el final de la misma, no todo.)

Hmm, bash no es lo que usaría para el procesamiento numérico de alta velocidad. Consigue una copia de GMP y prepara un programa C para hacerlo.

Bien puede haber una fórmula matemática para dártelo rápidamente, pero, en el tiempo que te lleva descubrirlo, GMP probablemente podría arrojarte el resultado: -)

Esto se identifica como secuencia A061418 en el sequences sitio (TAMBIÉN CONOCIDO COMO "La Enciclopedia en Línea de Secuencias de Enteros"); por la página correspondiente ,

FÓRMULA a(n) =A061419(n)+1 = ceiling[K*(3/2)^n] donde K=1.08151366859... La constante K es 2/3*K(3) (véase A083286).

Y con una biblioteca adecuada de alta precisión (GMP como ya se sugirió, o MPIR, y tal vez un envoltorio en la parte superior como my baby gmpy es para Python) puede utilizar la fórmula de forma cerrada para un cálculo mucho más rápido de "el artículo millonésimo de la serie" y similares.

A menudo es posible poner recurrencias especificadas recursivamente en fórmulas cerradas. Para una extensa introducción para principiantes al tema, Concrete Mathematics (por Graham, Knuth y Patashnik) es realmente difícil de superar.

Probablemente puedas acercarte un poco más usando un lenguaje más adecuado, por ejemplo, Scheme:

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

Esto calcula los 17610 dígitos de (series 100000) en aproximadamente 8 segundos en mi máquina. Desafortunadamente, (series 1000000) todavía toma demasiado tiempo para que incluso una máquina mucho más nueva/más rápida tenga alguna esperanza de terminar en un minuto.

Cambiando a C++ con una biblioteca de enteros grandes (NTL, en este caso):

#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;
}

Esto calcula la serie para 1000000 en 4 minutos, 35 segundos en mi máquina. Eso es lo suficientemente rápido que puedo casi creer que una máquina nueva realmente rápida podría al menos estar cerca de terminar en un minuto (y sí, comprobé lo que sucedió cuando usé turnos en lugar de multiplicación/división was fue más lento).

Desafortunadamente, el cálculo de forma cerrada que otros han sugerido parece ser de poca ayuda. Para usarlo necesitas calcular la constante K con suficiente precisión. No veo un cálculo de forma cerrada de K, por lo que esto realmente sólo cambia la iteración a la computación K, y parece que calcular K con suficiente precisión es poco (si lo hay) más rápido que calcular la serie original.

Es muy fácil de hacer en Pari:

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

Esto toma 14 segundos en mi máquina. Hay formas más rápidas, por supuesto GM GMP viene a la mente but pero ¿por qué molestarse? Usted no será capaz de afeitar más de 10 segundos fuera del tiempo de ejecución, y el tiempo de desarrollo sería del orden de minutos. :)

Punto menor: Es ambiguo en la formulación original si el₉₉₉₉₉₉ se desea o n_1000000, el número con índice un millón; I dar el último puesto que veo que el primero ya está calculado arriba.

Esta es casi una relación de recurrencia de primer orden, excepto por el piso, que arruina las cosas. Si no quisieras el piso,

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

Además, no uses bash.

La formulación recursiva va a tomar bastante tiempo bajo la mayoría curcumstances porque tiene que mantener la pila de la máquina. Por qué no usar dynamic ¿programando en su lugar?

Es decir, (pseudocódigo)

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

Por supuesto, para un resultado significativo necesitará una biblioteca de números de alta precisión.

Convertí las ideas de Timo en elisp. Falla con 100, dando un número negativo. FALLA, por favor, ver 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