Como encontrar o elemento da sequência Digit Sum com eficiência?

20

Apenas por interesse, tentei resolver um problema da categoria "Recente" do Projeto Euler ( sequência Digit Sum ). Mas não consigo pensar em uma maneira de resolver o problema com eficiência. O problema é o seguinte (na sequência de perguntas original tem duas no início, mas não altera a sequência):

A sequência da soma dos dígitos é 1,2,4,8,16,23,28,38,49 .... onde o termo da sequência é a soma dos dígitos que a precedem na sequência. Encontre o termo da sequência.nth1015th

A solução ingênua não pode ser implementada porque leva muito tempo. Tentei reduzir o problema a um caso de exponenciação da matriz (que levaria um tempo ), mas não consegui criar uma recorrência tão adequada aos critérios lineares, pois a recorrência para esta sequência é bastante peculiar. Pode-se ver que a sequência é governada pela recorrência:O(log(1015))

an=an1+d(an1).....(1)

onde é termo da sequência é uma função que, quando recebe um número natural como entrada, retorna a soma dos dígitos do número (por exemplo, ). Minha segunda abordagem foi tentar encontrar algum padrão na sequência. Pode-se observar que os primeiros termos da sequência podem ser escritos comoannthdd(786)=21

   a_1 = 1  
   a_2 = 1 + d( 1 )
   a_3 = 1 + d( 1 ) + d( 1 + d( 1 ) )
   a_4 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) )
   a_5 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) + d( 1 +  d(  
   1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) )

A partir do padrão acima, torna-se que termo da sequência pode ser gerado pelo seguinte método:nth

  1. Write é com o símbolo disso entre eles.2n1 1
  2. Deixando o primeiro , aplique a função nos próximos termos, depois nos próximos termos, depois nos próximos termos e assim por diante.1d202122
  3. Em seguida, aplique o método acima recursivamente nos argumentos de cada função aplicada.d

por exemplo, se n = 3, realizamos as seguintes manipulações:

    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
    1 + d( 1 ) + d( 1 + 1 ) + d( 1 + 1 + 1 + 1 )
    1 + d( 1 ) + d( 1 + d(1) ) + d( 1 + d( 1 ) + d( 1 +d( 1 ) ) )

Pela programação dinâmica, posso gerar o termo usando o método acima no tempo , que novamente não é melhor que a solução ingênua. O ( l o g ( 2 10 15 ) )nthO(log(21015))

EDIT 1
Outra coisa que pode ser observada é que . Por exemplo . Mas sou incapaz de fazer uso deste ponto. Tentei novamente encontrar uma relação de recorrência linear (para exponenciação da matriz), mas não consigo encontrá-la.d ( a 6 ) = d ( 23 ) = d ( 32 ) = 5d(an)=d(2n1)d(a6)=d(23)=d(32)=5

EDIT 2

A seguir, é apresentado o gráfico quando a sequência é plotada para um intervalo menor (os primeiros termos da sequência são plotados). 106insira a descrição da imagem aqui

PS: Eu sei que não é aconselhável pedir soluções ao Project Euler. Mas eu só quero uma nova direção ou uma dica, pois tenho andado em círculos nos últimos dias. Se isso também é inaceitável, posso remover a pergunta, se sugerido.

sashas
fonte
1
Eu sinto que You are given a106 = 31054319.no problema original de Euler é uma dica.
precisa saber é o seguinte
@FilipHaglund que não é uma dica. Como somente pela força bruta, posso calcular esse valor facilmente. É apenas para verificar sua abordagem.
Sashas 21/04
3
Também no OEIS: oeis.org/A004207 .
Yuval Filmus
@EvilJS poderia sim, plotei o gráfico em uma extensão, aumentando gradualmente de forma em zig zag. Você poderia elaborar o seu último ponto "" padrões de cache .. ".
Sashas
Dado que padrões interessantes aparecem no mod 9, algo interessante acontece se olharmos para a sequência mod 11 ou mod 99? O valor mod 11 pode ser derivado da soma dos dígitos indexados ímpares e da soma dos dígitos indexados pares. O valor mod 99 pode ser derivado da soma dos pares adjacentes de dígitos.
DW

Respostas:

4

Sua sequência é descrita em oeis.org/A004207 como a soma dos dígitos. Existem alguns pontos positivos, como a sequência mod 9 tem padrão de repetição , compartilha raízes digitais com oeis.org/A065075 e oeis.org/A001370 . Se essas propriedades forem úteis, é um problema aberto (porque não existe uma equação de forma fechada para o número). n - t h(1,2,4,8,7,5)nth

Há algumas propriedades dessa sequência que vale a pena mencionar:
Quando você calcula o número, é necessário armazenar apenas o contador (para saber qual era o número) e o próprio número. Para reiniciar, não é necessário mais nada, pois o próximo número é o número atual + soma dos dígitos.nth

Seguindo algumas etapas para garantir a velocidade, é bom colocar números em um array, evitando cálculos ingênuos de mod e div, que são caros. Isso acelera constantemente, mas, às vezes, isso importa.

Desde o ponto inicial, você pode calcular o próximo e o próximo, e funciona até certo ponto, esse mesmo ponto é o número de dígitos alterados.
O que é mais importante, os padrões estão mudando com o aumento dos números.
As somas de dígitos são pequenas em comparação com os próprios números; portanto, apenas a parte do número será alterada na maioria das operações.
Então, o que realmente podemos armazenar em cache?

Sabemos que, com dois números com a mesma soma de dígitos, a adição para obter o próximo número será a mesma. E o próximo?

sasha

Alerta de spoiler, abaixo está um padrão de cache bastante explícito

Depende de condições adicionais, como os números que não mudam na corrida , chamarei de turno , começando o valor como início .

Fazendo uma execução arbitrária , como , e começando de a , podemos armazenar em cache todos os padrões do ponto de partida até , contar o número de elementos (para saber como lidar com o contador, necessário para fornecer um número ) e memorize-o. 0 9 100 n - t h10009100nth

Está bem. Até agora, qualquer início é coberto, o que muda além de ? Infelizmente, esses padrões param de funcionar, porque se você tentar de tornando o início igual a , o próximo número será calculado perfeitamente, mas o segundo será interrompido. 100 1100
1001

Aqui, temos que cobrir o turno definido como e iniciar o definido como . Também significa calcular tabelas para diferentes turnos . 010

Nós realmente precisamos calcular todos eles ? Não, realmente não.
Parte das tabelas é apenas mais um item inicial.
Por exemplo, começando de fornece a mesma sequência deslocada. Então, precisamos calcular o cache mais longo? Não, calculamos isso para alterar as mudanças e realizar outra execução , economizando muita memória. 1,2,4,8

Agora, quando a tabela é coberta, começamos a partir da configuração inicial, selecionamos soma da tabela, adicionamos contador e vemos que: de chegamos a , atualizamos variáveis ​​e pulamos para , repetindo as etapas -> -> -> -> -> -> -> . Está bem. E agora? 101 218 305 406 517 607 719 805 904 100311012183054065176077198059041003

Podemos continuar até que o turno seja superior ao calculado.
Indo além, podemos criar mais execuções rapidamente, pré-calcular execuções maiores ou observar outros padrões (como podemos parcialmente reutilizar as tabelas já calculadas).
Dê uma olhada em diferentes turnos como todos eles dão a mesma execução, sendo o mesmo ambiente para somas de dígitos, portanto, podemos usar as mesmas tabelas. Fazer tabelas maiores que elementos acelera o processo, fazendo saltos maiores ao mesmo tempo.100100,1000,10000,100000,1000000...
100

Mal
fonte
4

Como você pediu "uma nova direção ou uma dica" e não sei a resposta, deixarei isso aqui, espero que seja útil. algumas ideias:

Faz sentido que haja um padrão 9, já que

k>1,kZ10k1mod9

O que você pode provar por indução.

Isso significa que todos os números são congruentes com a soma dos dígitos mod 9.

Além disso, an=d(an)mod9

an=an1+d(an1)=2d(an1)mod9

Se continuarmos expandindo essa recorrência, obtemos

an=2nmod9

O que explica o padrão mod 9.

Também nos dá . A cada iteração, obtemos uma lacuna divisível por 9. Qual a largura dessas lacunas?an=9k+2n

Aqui está um pouco abaixo do código geral:

import matplotlib.pyplot as plt
import numpy as np

#sum digits of n
def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

#get the sequence to n digits
def calculate(n):
    retval = [1]
    for i in range(n):
        retval.append(retval[-1] + sum_digits(retval[-1]))
    return retval;

#empirically confirm that a_n = 2^n mod 9
def confirmPow2(a):
    count = 0
    for i in a[:10000]:
        if((i%9) != (2**count % 9)):
            print "false"
        count = count + 1

#find gaps divisible by 9 in a subset of a
def find9Gaps(a):
    count = 0
    S = []
    for i in a[:10000]:
         S.append(((2**count ) - i)/9)
         count = count + 1
    return S

#repeatedly sum the digits until they're less than 9...
#gives some interesting patterns
def repeatedDigitSum():
    for i in range(1000, 1100):
         print "=========for ",i
         while i > 9:
                 i = sum_digits(i)
                 print i 


a = calculate(10**6)
b = find9Gaps(a)
plt.plot(range(len(b[:100])), b[:100])
plt.show()

O enredo (para os 100 primeiros) parece exponencial, mas não acho que seja perfeito.

plotagem de lacunas

Aqui está a saída de

>>> plt.plot(range(len(b[5:60])), np.log2(np.array(b[5:60])))
>>> plt.show()

gráfico logarítmico das lacunas

A última coisa que tenho é que parece que se você soma os dígitos de um número e depois soma os dígitos do número resultante e repita isso, você finalmente obtém esse número mod 9.

Faz sentido, dado o fato acima, sobre potências de 10 mod 9.

nd(n)d(d(n))mod9

No entanto, fornece uma sequência interessante de números.

Edit: Aparentemente, isso é chamado de "raiz digital".

quietContest
fonte
1
Foi meio que comentado pelo menos três vezes. Além disso, quando você faz um gráfico que parece exponencial para você, talvez você deva usar o logaritmo, informar sobre isso no eixo da escala? Se você plotasse 10 ^ 16 termos legíveis, eu ficaria realmente impressionado.
Mal
O que foi comentado 3 vezes? As pessoas estavam dizendo que havia um "padrão mod 9", mas eu senti que não estava claro o que era. Acabei de explorar e comentei o que tinha, pois acho que não poderei continuar trabalhando nisso. Novamente, não tenho uma solução, mas a pergunta não pediu uma.
usar o seguinte código
Adicionado um gráfico log por EvilJS sugestão, não pode traçar qualquer maior porque breaks numpy e eu realmente não tenho tempo para continuar a perseguir esse problema
quietContest