Проверка, генерируется ли элемент в определенной функции

Question

У меня есть функция, т.е.

f (n) = (2 * f (n-1)) - (2 * f (n-2)), где f (0) = 0 и f (1) = 1

У меня есть список (num_list). Как проверить, были ли элементы num_list сгенерированы функцией f (n). Где n> 1.

Answer 1

Это линейное рекуррентное соотношение, поэтому f (n) можно записать в замкнутой форме. Отношение повторения:

f (n + 2) - 2f (n + 1) + 2f (n) = 0

, так как левая часть линейный и правая часть равна нулю, это более простая форма более общей задачи решения линейного рекуррентного отношения: нам не нужно находить «конкретное решение», чтобы удовлетворить правую часть, просто общего решения "достаточно.

Общее решение можно найти, решив уравнение f (n) = x ⁿ , чтобы найти значения x, удовлетворяющие рекуррентному соотношению. Подставляя и упрощая, мы получаем квадратное c уравнение:

x ² - 2x + 2 = 0

Решения для этого Уравнением являются комплексные числа x = 1 + i и x = 1 - i, где i - это мнимая единица . Из линейности следует, что любая функция вида

f (n) = a (1 + i) ⁿ + b (1 - i) ⁿ

- это решение; подставляя граничные условия f (0) = 0 и f (1) = 1, получаем a = −i / 2 и b = i / 2. Итак, выражение для закрытой формы для f (n):

f (n) = (i / 2) ((1 - i) ⁿ - (1 + i) ) ⁿ )

Это можно переписать, применив формулу Эйлера , поскольку мы знаем, что f (n) всегда является действительным числом:

f (n) = (-1/2) (√2) ⁿ Im (e ^{−nπ / 4} - e ^{nπ / 4} ) = (√2) ⁿ sin (nπ / 4)

Выражение sin (nπ / 4) - это последовательность [0, 1/√2, 1, 1/√2, 0, −1/√2, −1, −1/√2, ...], которая повторяется с периодом 8. Отсюда следует, что для каждого натурального числа k последовательность принимает значения:

• f (8k) = f (8k + 4) = 0
• f (8k + 1) = 2 ^4k
• f (8k + 2) = f (8k + 3) = 2 ^{4k + 1}
• f (8k + 5) = −2 ^{4k + 2}
• f (8k + 6) = f (8k + 7) = −2 ^{4k + 3}

Следовательно, функция генерирует число тогда и только тогда, когда оно имеет одну из этих форм.

Answer 2

Симпси rsolve можно использовать для нахождения общей формулы для рекурсии.

from sympy import rsolve, Function, log
from sympy.abc import n

f = Function('f', real=True)
T = f(n) -   (2* f(n-1) - 2* f(n-2))
s = rsolve(T, f(n), {f(0): 0, f(1): 1})
print ("solution for n:", s)
'''I*((1 - I)**n - (1 + I)**n)/2'''

for k in range(10):
    print(k, s.subs(n, k).simplify())

Для этого конкретного уравнения решение включает в себя надоедливые мнимые числа, а симпози трудно упростить уравнение для больших n , Для более простых уравнений либо s.subs(n, k).simplify(), либо s.subs(n, k).evalf() должны дать адекватный ответ даже для больших n.

Как отмечено @JasonChia и с учетом того факта, что вас интересует только знание, может ли число быть Сгенерировано или нет, можно также просто посмотреть на последовательность:

[0, 1, 2, 2, 0, -4, -8, -8, 0, 16, 32, 32, 0, -64, -128, -128, 0, 256, 512, 512, 0, -1024, -2048, -2048, 0, 4096, 8192, 8192, 0, ...]

Все степени 2 вместе с 0 появляются, но либо как положительное, либо как отрицательное число. Отрицательные числа имеют вид 2 ^k , когда k mod 4 равно 2 или 3. И напишите некоторую функцию как:

def is_in_the_squence(x):
    if not isinstance(x, int):
        return False
    elif x == 0:
        return True
    else:
        k = 0
        while x != 1 and x != -1:
            k += 1
            if x % 2 != 0:
                return False
            x //= 2
        return ( x == -1 and k % 4 >= 2) or ( x == 1 and k % 4 < 2)

Answer 3

Вы можете проанализировать саму функцию, а не использовать метод грубой силы. Глядя на вольфрама, должно быть какое-то условие, чтобы проверить, существует ли он. Глядя на первые 13 значений:

[0,1,2,2,0, -4, -8, -8,0,16,32,32,0]

Думаю, если вы посмотрите на

log2 (abs (f (n))) -> [-, 0,1,1,2,3,3, -, 4 , 5,5, -]

Логически упрощено до [0,1,1,2,3,3,4,5,5], игнорируя 0s.

Итак, мы есть образец. Я думаю, что это разрешимо таким образом, что:

Так что, если значение abs (num) является целым числом. Возможно быть частью шаблона. Затем нам нужно проверить значения, если они должны быть отрицательными или положительными.

Разбивка дальше: положительные значения [0,1,1,4,5,5,8,9,9, ... ] Отрицательные значения [2,3,3,6,7,7,10,11,11 ...]

Затем мы можем проверить, если n% 4 == 0 или (n-1)% 4 == 0. Если это правда и исходное значение положительно -> чем да, оно было сделано из f (n) Если ложно и исходное значение отрицательно -> также сделано из f (n)

в противном случае оно wasnt.

import numpy as np
def test(x):
    if x == 0 or x == 1:
        return True
    if x == -1 or x == -2:
        return False
    val = np.log2(abs(x))
    if val%1==0:
        if(val%4 == 0 or (val-1)%4==0) and x >0:
            return True
        elif (val%4!=0 and (val-1)%4 != 0) and x <0:
            return True
        else:
            return False
    else:
        return False

Я не даю никаких гарантий, что моя математика верна. Протестировал и, кажется, работает. Там могут быть некоторые математические ошибки.