Вычислить число представлений числа в виде суммы чисел фибоначчи

Ответ 1

Докажите немного вещей о числах:

Лемма 1. Пусть n ≥ 1 - целое число, а Fib (i) - наибольшее число Фибоначчи с Fib (i) ≤ n. Тогда в представлении n в виде суммы чисел Фибоначчи с различными индексами появляется либо Fib (i), либо Fib (i-1), но не оба.

Доказательство. По индукции мы можем показать, что сумма Fib (1) + Fib (2) +... + Fib (i - 2) = Fib (i) - 1. Так как Fib (i) n, нам нужно, по крайней мере, Fib (i-1) или Fib (i) в представлении. Но не оба, так как Fib (i) + Fib (i - 1) = Fib (i + 1) > n (иначе Fib (i) не будет максимальным числом Фибоначчи, меньшим или равным n).

Лемма 2: n - Fib (i) < Fib (i - 1) и n - Fib (i - 1) Фибо (я).

Доказательство. Это легко показать. Оставленный как упражнение для читателя.

Осталась последняя проблема: как вычислить i? Одно из важных наблюдений заключается в том, что числа Фибоначчи растут экспоненциально, поэтому мы имеем я = O (log n). Мы можем просто использовать грубую силу, чтобы ее найти (вычислить все числа Фибоначчи до n:

function F(n : Integer, recurseHigh = True: Bool):
    if n == 0: return 1
    a, b = 1, 1
    while a + b <= n:
        a, b = b, a + b
    res = 0
    if recurseHigh: res += F(n - b)
    res += F(n - a, n - a < a)
    return res

Случается, что он работает достаточно быстро даже с этой "глупой" реализацией для 32-битных целых чисел. Если вы используете memoization, он работает даже для гораздо больших чисел, но тогда вам нужна динамически распределенная память.

Я еще не доказал сложность выполнения во время выполнения, но он уверен, что это чертовски быстро, если используется memoization. Я думаю, что это O (log² n) дополнения и будет O (log n * log log n), если мы предварительно скопируем числа Фибоначчи с точностью до n и выполним двоичный поиск для i. Не уверен в этом случае без воспоминаний, но, похоже, он не работает с n выше 2³².

Вот некоторые значения F в случае, если вам интересно, вычислено с помощью memoized версии вышеуказанной функции в Python:

F(0) = 1
F(1) = 2
F(2) = 2
F(3) = 3
F(4) = 3
F(5) = 3
F(6) = 4
F(7) = 3
F(8) = 4
F(9) = 5
F(10) = 4
F(11) = 5
F(12) = 4
F(13) = 4
F(14) = 6
F(4079078553298575003715036404948112232583483826150114126141906775660304738681982981114711241662261246) = 70875138187634460005150866420231716864000000
F(2093397132298013861818922996230028521104292633652443820564201469339117288431349400794759495467500744) = 157806495228764859558469497848542003200000000
F(1832962638825344364456510906608935117588449684478844475703210731222814604429713055795735059447061144) = 9556121706647393773891318116777984000000000
F(6529981124822323555642594388843027053160471595955101601272729237158412478312608142562647329142961542) = 7311968902691913059222356326906593280000000
F(3031139617090050615428607946661983338146903521304736547757088122017649742323928728412275969860093980) = 16200410965370556030391586130218188800000000
F(4787808019310723702107647550328703908551674469886971208491257565640200610624347175457519382346088080) = 7986384770542363809305167745746206720000000
F(568279248853026201557238405432647353484815906567776936304155013089292340520978607228915696160572347) = 213144111166298008572590523452227584000000000
F(7953857553962936439961076971832463917976466235413432258794084414322612186613216541515131230793180511) = 276031486797406622817346654015856836608000000
F(2724019577196318260962320594925520373472226823978772590344943295935004764155341943491062476123088637) = 155006702456719127405700915456167116800000000
F(4922026488474420417379924107498371752969733346340977075329964125801364261449011746275640792914985997) = 3611539307706585535227777776416785118003200
F(10^1000) = 1726698225267318906119107341755992908460082681412498622901372213247990324071889761112794235130300620075124162289430696248595221333809537338231776141120533748424614771724793270540367766223552120024230917898667149630483676495477354911576060816395737762381023625725682073094801703249961941588546705389069111632315001874553269267034143125999981126056382866927910912000000000000000000000000000000000000000000000000000000000000000000000000000000

Заметим, что это похоже на F (n) = Θ (sqrt (n)), еще один результат, который я еще не доказал.

UPDATE: Здесь код Python:

memo = {}
def F(n, x=True):
    if n == 0: return 1
    if (n, x) in memo: return memo[n,x]
    i = 1
    a, b = 1, 1
    while b + a <= n:
        a, b = b, a + b
    memo[n,x] = (F(n - b) if x else 0) + F(n - a, n - a < a)
    return memo[n,x]

ОБНОВЛЕНИЕ 2. Вы можете улучшить время исполнения даже без memoization, используя двоичный поиск, чтобы найти я и вычислить Fib (i), используя быстрое экспоненциальное преобразование матрицы. Наверное, не стоит усилий, хотя, особенно не для 32-битного n.

ОБНОВЛЕНИЕ 3. Просто для удовольствия, вот реализация, которая доказуемо добавляет только O(log n):

fib = [0,1]
def greedy(n):
    while fib[-1] < n:
        fib.append(fib[-1] + fib[-2])
    i = 1
    while fib[i+1] <= n: i += 1
    digs = set()
    while n:
        while fib[i] > n: i -= 1
        digs.add(i)
        n -= fib[i]
    return digs

def F(n):
    digs = greedy(n)
    top = max(digs)
    dp = [[[0,0,0] for _ in xrange(4)] for _ in xrange(top+1)]
    for j in xrange(0, 2): dp[0][j][0] = 1
    for i in xrange(1, top + 1):
        for j in xrange(0,2):
            for k in xrange(0,j+1):
                if i in digs:
                    dp[i][j][k] = dp[i-1][k+j][j] + dp[i-1][k+j+1][j+1]
                else:
                    dp[i][j][k] = dp[i-1][k+j][j] + dp[i-1][k+j-1][j-1]
    return dp[top][0][0]

Сначала он обнаруживает жадное представление числа в базе фибоначчи, а затем использует DP, чтобы найти количество способов переноса цифр в этом представлении, чтобы создать окончательное число. dp[i,j,k] - количество способов представления префикса 1..i числа в базе фибоначчи, если мы переносим j на позицию i и переносим k на позицию i - 1. Используя это, мы можем вычислить F(10^50000) менее чем за 5 секунд (результат имеет более 20000 десятичных цифр!)

Ответ 2

Меня заинтриговали два аспекта Niklas B.: скорость вычислений (даже для огромных чисел), а также тенденция к получению небольших главные факторы. Эти намеки на то, что решение можно вычислить как произведение малых членов, и это действительно так.

Чтобы объяснить, что происходит, мне нужны некоторые обозначения и терминология. Для любого неотрицательного целого n я определю (уникальное) жадное представление of n как сумму чисел Фибоначчи, полученных путем повторного принятия наибольшего числа Фибоначчи, не превышающего n. Так, например, жадным представлением 10 является 8 + 2. Легко заметить, что мы никогда не используем Fib(1) в таком жадном представлении.

Мне также нужен компактный способ записи этих представлений, и для этого я собираюсь использовать битстроны. Подобно бинарным, за исключением того, что значения места следуют последовательности Фибоначчи вместо последовательности степеней 2, и я сначала напишу наименее значащую цифру. Например, 00100001 имеет 1 в позиции 2 и позиции 7, поэтому представляет Fib(2) + Fib(7) = 1 + 13 = 14. (Да, я начинаю считать с 0 и следуя обычному соглашению, что Fib(0) = 0.)

Скорее всего, поиск всех представлений начинается с жадного представления, а затем исследовать все возможности переписывания подшаблона формы 001 как шаблон формы 110; т.е. заменяя Fib(k+2) на Fib(k) + Fib(k+1) для некоторого k.

Таким образом, мы всегда можем написать жадное представление n в качестве битовой строки, а эта строка будет последовательностью 0 и 1 s, без двух смежных 1 s. Теперь основное замечание состоит в том, что мы можем разбить эту битструю на куски и вычислить количество переписывающих для каждой отдельной части, умножая их на общее количество представлений. Это работает, потому что некоторые подшаблоны в битовой строчке препятствуют взаимодействию между правилами перезаписи для части строки слева от шаблона и справа.

В качестве примера рассмотрим n = 78. Его жадное представление 00010000101, и подход грубой силы быстро идентифицирует полный набор представлений. Их десять:

00010000101
01100000101
00010011001
01100011001
00011101001
01101101001
0001001111
0110001111
0001110111
0110110111

Мы можем отделить первую часть рисунка, 0001, от второго, 0000101. Каждая из вышеперечисленных комбинаций состоит из перезаписи 0001, отдельно переписывающей 0000101 и склеивания двух переписываемых вместе. Для левой части шаблона есть 2 перезаписи (включая оригинал), а 5 - справа, поэтому мы получаем 10 представлений в целом.

Что делает эта работа, так это то, что любая пересылка левой половины, 0001, заканчивается либо 01, либо 10, а любая переписка правой половины начинается с 00 или 11. Поэтому нет совпадений ни для 001, ни для 110, которые перекрывают границу. Мы получим это разделение всякий раз, когда у нас есть два 1, разделенных четным числом нулей.

И это объясняет малые простые факторы, наблюдаемые в ответе Никласа: в произвольно выбранном числе будет много последовательностей 0 четной длины, и каждый из них представляет точку, в которой мы можем разделить вычисление.

Объяснения становятся немного запутанными, поэтому здесь приведен код Python. Я подтвердил, что результаты согласуются с Niklas для всех n до 10**6 и для выбора случайным образом выбранного большого n. Он должен иметь такую ​​же алгоритмическую сложность.

def combinations(n):
    # Find Fibonacci numbers not exceeding n, along with their indices.
    # We don't need Fib(0) or Fib(1), so start at Fib(2).
    fibs = []
    a, b, index = 1, 2, 2
    while a <= n:
        fibs.append((index, a))
        a, b, index = b, a + b, index + 1

    # Compute greedy representation of n as a sum of Fibonacci numbers;
    # accumulate the indices of those numbers in indices.
    indices = []
    for index, fib in reversed(fibs):
        if n >= fib:
            n -= fib
            indices.append(index)
    indices = indices[::-1]

    # Compute the 'signature' of the number: the lengths of the pieces
    # of the form 00...01.
    signature = [i2 - i1 for i1, i2 in zip([-1] + indices[:-1], indices)]

    # Iterate to simultaneously compute total number of rewrites,
    # and the total number with the top bit set.
    total, top_set = 1, 1
    for l in signature:
        total, top_set = ((l + 2) // 2 * total - (l + 1) % 2 * top_set, total)

    # And return the grand total.
    return total

EDIT: код существенно упрощен.

ИЗМЕНИТЬ 2: Я снова наткнулся на этот ответ и предположил, что существует более простой способ. Здесь еще одно упрощение кода, ясно показывающее, что требуются операции O(log n).

def combinations(n):
    """Number of ways to write n as a sum of positive
    Fibonacci numbers with distinct indices.
    """
    # Find Fibonacci numbers not exceeding n.
    fibs = []
    fib, next_fib = 0, 1
    while fib <= n:
        fibs.append(fib)
        fib, next_fib = next_fib, fib + next_fib

    # Compute greedy representation, most significant bit first.
    greedy = []
    for fib in reversed(fibs):
        greedy.append(fib <= n)
        if greedy[-1]:
            n -= fib

    # Iterate to compute number of rewrites.
    x, y, z = 1, 0, 0
    for bit in reversed(greedy):
        x, y, z = (0, y + z, x) if bit else (x + z, z, y)
    return y + z

Ответ 3

Вы можете найти лексикографически наибольшее представление 0/1 в базе Фибоначчи, взяв наибольшее число Фибоначчи, меньшее или равное вашему числу, вычтите его, а затем возьмите следующее наибольшее число Фибоначчи, меньшее или равное остатку, и т.д. Тогда возникает вопрос, как найти все остальные 0/1 представления в базе Фибоначчи из лексикографически наибольшей. Я считаю, что вы можете использовать отношение повторения Фибоначчи для этого. Например, если ваше представление равно 1100... тогда вы можете заменить 2-е наибольшее число Fib в представлении суммой следующих двух, давая 1011..... Если вы рекурсивно обрабатываете строку таким образом слева направо повторно, либо выбирая сделать замену или нет, когда можете, и используя динамическое программирование, чтобы помнить, какие представления вы уже изучили, я считаю, что вы получите все представления и в O (m log n) время, где m - общее число представлений Фибоначчи для вашего номера n. Я обновлю, если найду окончательное доказательство этого. Тем временем вы можете проверить гипотезу о количестве до примерно миллиона или около того. Если он проверяет все эти случаи, то это почти наверняка верно в целом.

Ответ 4

Одна из наивных возможностей в python (работает до 10 ^ 6 в разумные сроки)

def nfibhelper(fibm1,fibm2,n):
    fib = fibm1 + fibm2
    if fib > n:
        return 0
    r=0
    if n == fib :
        r+=1
    return r + nfibhelper(fibm2,fib,n-fib) + nfibhelper(fibm2,fib,n)


def F(n):
    return nfibhelper(1,0,n) ##1 will be used twice as fib