是否有一种更加Pythonic的编码这种递归关系的方法:OEIS A077947

问题描述 投票:0回答:3

我正在研究关于Jacobsthal序列的论文(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代码,这些序列在种子值a-f处开始。计算给定A077947 a(n)所需的迭代次数为~n / 6。执行时的代码将A077947的所有值返回到范围(x)或A077947的~x * 6项。当我在序列中寻找周期性数字根保存作为识别数据中模式的方法时,我发现重复的数字根很有趣。例如,数字根保留序列可以在估算经过维护的大型IT生态系统(mod7环境)中的警报的真或假状态时,对大型数据集进行时间序列分析;这种分析还与预测消费者需求/行为模式有关。利用这些分析方法,将A077947划分为6个数字根保留序列,旨在降低复杂性; Python代码使用种子值a-f在6个“通道”上重现A077947。这段长篇归结为声明,“序列术语的数字根源在模式中重复(1,1,2,5,9,9)。”更大的说法是,数字根与模式重复的所有序列可以被分割/分离成相同数量的不同序列,并且这些序列可以独立计算。有一个与这个序列有关的赏金。

这段代码很难看,但如果没有这样编码,我似乎无法得到正确的答案;

我还没有弄清楚如何将其写为函数,因为我似乎无法将重复值正确存储在函数中。

因此,如果这会产生良好的结果,我们希望将讨论与OEIS参考文献联系起来。

这是序列的链接:https://oeis.org/A077947

python math recurrence oeis
3个回答
2
投票

这是另一种没有第二个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

使用functools的reduce函数可以使这更加简洁:

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功能。

我相信你并不总是需要一系列乘法器来计算每个通道的下一个值。对函数的改进是为lambda函数提供通道索引而不是乘数。如果需要,这将允许您使用一个乘数数组,但也允许您使用更一般的计算。

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) ]

lambda函数有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])

或(基于2 * S + i%3 - 1的6个频道):

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)


0
投票

这将与您的代码完全相同,并且可以说更漂亮。您可能会看到使魔术常数不那么随意的方法。

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固定就足够了。


0
投票

这是使用生成器的替代版本:

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))
© www.soinside.com 2019 - 2024. All rights reserved.