Ciąg z sumą liczb

a_n+1 = a_n + suma cyfr a_n
a_10⁶ = 31054319.
a_10¹⁵ = ?

suma cyfr to innaczej, log10(an). Wiedząc to można łatwo policzyć ilość iteracji przy których an się wydłuży o jedną cyfrę, obliczasz wartość tej iteracji (zwykłe mnożenie), i powtarzasz do skutku od aktualnego ptk ;),Jaeśli nie musisz bawić się w aptekę moze da rade to analitycznie to scałkować.

topik92 napisał(a):

suma cyfr to innaczej, log10(an). Wiedząc to można łatwo policzyć ilość iteracji przy których an się wydłuży o jedną cyfrę, obliczasz wartość tej iteracji (zwykłe mnożenie), i powtarzasz do skutku od aktualnego ptk ;),Jaeśli nie musisz bawić się w aptekę moze da rade to analitycznie to scałkować.

Co to znaczy log10(an)? Jaka wg tego wzoru jest suma cyfr liczby 123?

W końcu musi się to redukować do mnożenia...
Jest minuta na rozwiązanie.
Biorąc pod uwagę ilość operacji 10¹⁵ - 10⁶ to prawie 10¹⁵.
Nawet przed oficjalnym commitem metodą brute force trwałoby okropnie długo.

Nie wiem czy tak da rade to rozwiązać ale może Ci pomoże.
Zakres dodawanych liczb co iteracje można oszacować na od kilku do max 200. Z tego wynika ze o ile sama końcówka zmienia się dość chaotycznie, o tyle wszystko od 4 pozycji w górę zmienia maksymalnie o jeden, jak w zegarku i jest przewidywalna.
Między zakresam przyrostów 0-200 a końcówką 000-999 jest tylko 200k kombinacji, można to ztablicować do formy dla przyrostu o 21 i końcówki 023 otrzymuje końcówkę 044 i zwrost o x, i wykonuje 1 skok. Ponieważ 200k jest znacznie mniejsze od 10^15, to wykonując obliczenia na zasadzie skoków między wynikami tablicy będziesz musiał kluczyć(trafaić na te same wyniki), gdybyś co skok uaktualniał tablice to to co iteracje robił byś skoki o setki ,tysiące, lub setki tysięcy n na naraz. Problemem jest że trzeba w jakiś sposób uaktualniać uaktualniać wartość przyrostu, a nie można robić tego co każdy wzrost o 1000, gdyby udało się to powiązać z spamiętanymi skokami, to by było super. Gdybyś przechowywał sume przyrostów, i liczbe skoków w osobnych zmiennych i wpisał tam wartości początkowe, a w miejsce wartości początkowych w pisać zera, to odszedł by Ci specjalny przypadek do uwzględniania, niby pierdoła ale upraszcza sprawę. ed. [zamiast zer i "pełnych wartosci" mozna wpisać dowolne liczby tak by najlepiej Ci się liczyło ]
Opcja b)
Licz przez tydzień i na commit napisz return wartość :D,

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

constexpr uint64_t maxcount=1000000;
constexpr uint64_t mincount=1;

uint64_t brute(uint64_t value)
  {
   cout<<'\r'<<mincount<<' '<<value<<endl;
   for(uint64_t i=mincount;i<maxcount;++i)
     {
      uint64_t add=0;
      for(uint64_t div=value,next=0;div;div=next) add+=div-10*(next=div/10);
      value+=add;
     }
   cout<<'\r'<<maxcount<<' '<<value<<endl;
  }

int main()
  {
   brute(27675023);
   return 0;
  }

Zastanawia mnie sposób jak to liczycie. Bo z komentarzy @bogdans wynika (pomijając błąd), że startuje od jakiejś wartości i do kolejnej dodaje sumę cyfr. Podobnie działa powyższe rozwiązanie @_13th_Dragon.
Ze wzoru an+1 = an + suma cyfr an jak dla mnie wynika, że kolejna wartość to aktualna + suma cyfr tej aktualnej.
Sprawdziłem to sobie wtedy na szybko jak zachowa się dla a₁ = 1 i dostaję wartość taką jak się spodziewałem.

public class Main {

    public static void main(String [] args) {

        int sum = 1;

        for(int i = 1; i < 1000000; ++i)
            sum +=  getDigits(sum);
        System.out.println(sum);
    }

    public static int getDigits(int num) {
        int sum = 0;
        while (num > 0) {
            sum = sum + num % 10;
            num = num / 10;
        }
        return sum;
    }
}

Kto z nas źle rozumie to zadanie?

Oblicz dla 200 tysięcy kombinacji o których pisalem wszystkie możliwe sposoby uzyskania tysiąca. Korzystając z poprzednich wyników oblicz wszystkie sposoby uzyskania 10k, potem 100k potem miliona itd. aż do 10^20 to i tak za duzo. bedzisz potrzebował maksymalnie k*(20-3)*200 000 operacji(k w okolicach 10 ilosć kroków by przejsc z z tysiaca an 10 itd.) i między 0,2 a 2 Giga ramu, Korzystając z tych wyników złoż swoją liczbe.

Oblicz dla 200 tysięcy kombinacji o których pisalem wszystkie możliwe sposoby uzyskania tysiąca.

Proszę wyjaśnić, bo nie do końca rozumiem.

Złoty Pomidor napisał(a):

Oblicz dla 200 tysięcy kombinacji o których pisalem wszystkie możliwe sposoby uzyskania tysiąca.

Proszę wyjaśnić, bo nie do końca rozumiem.

Ja też się dołączam do apelu o wyjaśnienie.

Do kotków. Każda kolejna liczba zalezy od wartosci przyrostu. Przyrost zależy od sumy wszystkich aktualnych cyfr, i można go oszacować(przy założeniu wyniku rzędu[jak to naprawić??>>] 10 ^{20) . w zakresie od 1 do 20 * 9 = 180 dla uproszczenia 200. Przyrost zmienia się co iteracje ale jako ze 200 ma się nijak do 10}15 -dolne oszacowanie wyniku -to większość cyfr pozostaje taka sama lub zmienia się w przewidywalny (sposób o +1 modulo 10). Natomiast 3 najmniej znaczace cyfry zmieniają sie bardzo gwałtownie. Nie umiem zgadnąć co tam się dzieje , wiec zamiast zgadywać tablicuje sobie zmianę końcówki w funkcji przyrostu i aktualnej koncowki 0-999 x 1-200 daje ~200 000 kombinacji. Przyrost pochodzący od części wolno zmiennej nie zmienia sie dopóki nie zmieni się 4 cyfra po przecinku, a ta się zmienia gdy "zrobimy" tysiąc. Obliczamy sposoby osiągnięcia najmiejszej wartosi powyzej wartości tysiąca, dla wszystkich 200k danych początkowych i je tablicujemy, tak żeby zapamietac uzyskaną końcówkę.
Teraz z tych tysięcy do kolejnej tablicy 200k składamy sposoby osiągnięcia 10k, ktoś mógłby powiedzieć chola chola przecież zmienia się nam sie 4 liczba po przecinku, tak ale zmienia się ona maksymalnie o 1, w przewidywalny sposób, i bardzo latwo to uwzględnić podczas składania.
Robimy analogicznie dla kolejnych rzedów wartości. Warto zauważyć że przy obliczaniu np. 100k, robiąc kroki o 10k + 0-200, wartość na 4 pozycji jest się nie zmienia ;). Zapomniałem napisac że oprócz koncowki trzeba pamiętać liczbę wykonanych podstawowych kroków.
Jak masz już te te tablice robisz w mniej lub bardziej zgrabny sposób skoki o absurdalne wartośći n i odnajdujesz wynik w kilku krokach. Wartości skoku to wartość kubełka plus z tablicowana koncówka plus koncówka z "poprzedniego kroku".

[gdyby zamiast od najpierw liczyć wszystko a potem wybierać, liczyć na bieżąco tylko to co konieczne to, liczba operacji na pewno by znacznie zmalała]