Есть ли более Pythonic способ кодирования этого рекуррентного отношения re: OEIS A077947
Я работаю над тезисом о последовательностях Якобсталя (A001045) и о том, как их можно рассматривать как состоящие из некоторого числа различных подпоследовательностей. Я сделал комментарий к A077947, указав это, и включил программу на Python. К сожалению, написанная программа оставляет желать лучшего, и поэтому я, конечно, хотел обратиться к Stack, чтобы посмотреть, знает ли кто-нибудь здесь, как улучшить код!
Вот код:
a=1
b=1
c=2
d=5
e=9
f=18
for x in range(0, 100):
print(a, b, c, d, e, f)
a = a+(36*64**x)
b = b+(72*64**x)
c = c+(144*64**x)
d = d+(288*64**x)
e = e+(576*64**x)
f = f+(1152*64**x)
Я объясняю причины этого следующим образом:
Последовательность A077947 генерируется 6 цифровыми последовательностями, сохраняющими корни, сшитыми вместе; согласно коду Python эти последовательности инициируются при начальных значениях af. Число итераций, необходимое для вычисления данного A077947 a(n), составляет ~n/6. Код при выполнении возвращает все значения для A077947 вплоть до диапазона (x) или ~x*6 членов A077947. Я нахожу повторяющиеся цифровые корни интересными, так как я ищу периодическое сохранение цифровых корней в последовательностях как метод для определения закономерностей в данных. Например, последовательности сохранения цифрового корня позволяют анализировать временные ряды больших наборов данных при оценке истинного или ложного состояния для аварийных сигналов в крупных ИТ-экосистемах, которые подвергаются обслуживанию (среды mod7); такой анализ также связан с прогнозированием потребительского спроса / моделей поведения. Используя эти методы анализа, разделение A077947 на 6 последовательностей, сохраняющих цифровой корень, должно было уменьшить сложность; код Python воспроизводит A077947 через 6 "каналов" со начальными значениями af. Этот длинный абзац сводится к утверждению: "Цифровые корни терминов последовательности повторяются в схеме (1, 1, 2, 5, 9, 9)". Большее утверждение состоит в том, что все последовательности, цифровые корни которых повторяются с шаблоном, могут быть разделены / разделены на равное количество различных последовательностей, и эти последовательности могут быть вычислены независимо. Был щедрость, связанная с этой последовательностью.
Этот код уродлив, но я не могу получить правильный ответ, не написав его таким образом;
Я не понял, как написать это как функцию из-за того, что я не могу получить значения рекуррентности для правильного хранения в функции.
Поэтому, конечно, если это даст хорошие результаты, мы надеемся связать обсуждение со ссылками OEIS.
Вот ссылка на последовательность: https://oeis.org/A077947
3 ответа
Вот альтернативный способ сделать это без второго цикла for:
sequences = [ 1, 1, 2, 5, 9, 18 ]
multipliers = [ 36, 72, 144, 288, 576, 1152 ]
for x in range(100):
print(*sequences)
sequences = [ s + m*64**x for s,m in zip(sequences,multipliers) ]
[РЕДАКТИРОВАТЬ] Глядя на значения, я заметил, что эту конкретную последовательность также можно получить с:
N [i + 1] = 2 * N [i] + (-1,0,1 в ротации)
или же
N [i + 1] = 2 * N [i] + i mod 3 - 1 (при условии, что индекс равен нулю)
i N[i] [-1,0,1] N[i+1]
0 1 -1 --> 2*1 - 1 --> 1
1 1 0 --> 2*1 + 0 --> 2
2 2 1 --> 2*2 + 1 --> 5
3 5 -1 --> 2*5 - 1 --> 9
4 9 0 --> 2*9 + 0 --> 18
...
Таким образом, более простой цикл для создания последовательности может быть:
n = 1
for i in range(100):
print(n)
n = 2*n + i % 3 - 1
Использование функции Reduction от functools может сделать это еще более кратким:
from functools import reduce
sequence = reduce(lambda s,i: s + [s[-1]*2 + i%3 - 1],range(20),[1])
print(sequence)
>>> [1, 1, 2, 5, 9, 18, 37, 73, 146, 293, 585, 1170, 2341, 4681, 9362, 18725, 37449, 74898, 149797, 299593, 599186]
Используя ваш многоканальный подход и предложенную мной формулу, это даст:
sequences = [ 1, 1, 2, 5, 9, 18 ]
multipliers = [ 36, 72, 144, 288, 576, 1152 ]
allSequences = reduce(lambda ss,x: ss + [[ s + m*64**x for s,m in zip(ss[-1],multipliers) ]],range(100),[sequences])
for seq in allSequences: print(*seq) # print 6 by 6
[EDIT2] Если у всех ваших последовательностей будет одинаковый шаблон (т.е. начальные каналы, множители и формула расчета), вы можете обобщить вывод таких последовательностей в функцию, поэтому для каждой последовательности требуется только одна строка:
def printSeq(calcNext,sequence,multipliers,count):
for x in range(count):
print(*sequence)
sequence = [ calcNext(x,s,m) for s,m in zip(sequence,multipliers) ]
printSeq(lambda x,s,m:s*2+m*64**x,[1,1,2,5,9,18],multipliers=[36,72,144,288,576,1152],count=100)
[EDIT3] Улучшение функции printSeq.
Я считаю, что вам не всегда нужен массив множителей для вычисления следующего значения в каждом канале. Улучшение функции будет заключаться в предоставлении индекса канала для лямбда-функции вместо множителя. Это позволит вам использовать массив множителей, если вам нужно, но также позволит вам использовать более общие вычисления.
def printSeq(name,count,calcNext,sequence):
p = len(sequence)
for x in range(count):
print(name, x,":","\t".join(str(s) for s in sequence))
sequence = [ calcNext(x,s,c,p) for c,s in enumerate(sequence) ]
Функция лямбда имеет 4 параметра и, как ожидается, вернет следующее значение последовательности для указанного канала:
s : current sequence value for the channel
x : iteration number
c : channel index (zero based)
p : number of channels
Таким образом, использование массива внутри формулы будет выражать это так:
printSeq("A077947",100,lambda x,s,c,p: s + [36,72,144,288,576,1152][c] * 64**x, [1,1,2,5,9,18])
Но вы также можете использовать более общую формулу, основанную на индексе канала (и количестве каналов):
printSeq("A077947",100,lambda x,s,c,p: s + 9 * 2**(p*x+c+2), [1,1,2,5,9,18])
или ( 6 каналов на основе 2*S + i%3 - 1):
printSeq("A077947",100,lambda x,s,c,p: 64*s + 9*(c%3*2 - (c+2)%3 - 1) ,[1,1,2,5,9,18])
printSeq("A077947",100,lambda x,s,c,p: 64*s + 9*[-3,1,2][c%3],[1,1,2,5,9,18])
Я рассуждаю здесь так: если у вас есть функция, которая может вычислить следующее значение на основе текущего индекса и значения в последовательности, вы сможете определить шаговую функцию, которая будет вычислять значение, которое на N индексов дальше.
Дано F(i,S[i]) -> i+1,S[i+1]
F2(i,S[i]) --> i+2,S[i+2] = F(F(i,S[i]))
F3(i,S[i]) --> i+3,S[i+3] = F(F(F(i,S[i])))
...
F6(i,S[i]) --> i+6,S[i+6] = F(F(F(F(F(F(i,S[i]))))))
...
Fn(i,S[i]) --> i+n,S[i+n] = ...
Это всегда будет работать и не должно требовать массив множителей. Большую часть времени должно быть возможно упростить Fn, используя простую алгебру.
например, A001045: F(i,S) = i+1, 2*S + (-1)**i
printSeq("A001045",20,lambda x,s,c,p: 64*s + 21*(-1)**(x*p+c),[0,1,1,3,5,11])
Обратите внимание, что начиная с 3-го значения, следующее значение в этой последовательности может быть вычислено без знания индекса:
A001045: F (S) = 2 * S + 1 - 2 * 0 ** ((S + 1)% 4)
Вот альтернативная версия с использованием генераторов:
def Jacobsthal():
roots = [1, 1, 2, 5, 9, 18]
x = 0
while True:
yield roots
for i in range(6):
roots[i] += 36 * 2**i * 64**x
x += 1
И вот безопасный способ его использования:
j = Jacobsthal()
for _ in range(10):
print(j.send(None))
Это будет вести себя идентично вашему коду, и, возможно, красивее. Вы, вероятно, увидите способы сделать магические константы менее произвольными.
factors = [ 1, 1, 2, 5, 9, 18 ]
cofactors = [ 36*(2**n) for n in range(6) ]
for x in range(10):
print(*factors)
for i in range(6):
factors[i] = factors[i] + cofactors[i] * 64**x
Чтобы вычислить только одну из подпоследовательностей, было бы достаточно сохранить i исправлено во время итерации.
Как видно из аннотации OEIS, вам нужны только 3 начальных значения и 1 рекурсия из 3 предыдущих элементов последовательности, a(n-1), a(n-2) и a(n-3). После этого вы легко сможете получить серию.
# a(n-1)+a(n-2)+2*a(n-3)
# start values: 1, 1, 2
a1, a2, a3 = 1,1,2 #initial vales
m3, m2, m1 = 1,1,2 #multipliers for a(n-1):m3 a(n-2):m2 and a(n-3):m1
print a1, a2, a3,
for i in range(16):
a1,a2,a3=a2,a3,a3*m3+a2*m2+a1*m1
print a3,
Это дает вам 1 1 2 5 9 18 37 73 146 293 585 1170 2341 4681 9362 18725 ...