Alec: New page: This is a simple Python script to search for all completely multiplicative sequences of successively greater length. At the top of the script, 'N' is the limit of the search, and 'limit' i...

2010-01-13T09:38:05Z

New page: This is a simple Python script to search for all completely multiplicative sequences of successively greater length. At the top of the script, 'N' is the limit of the search, and 'limit' i...

New page

This is a simple Python script to search for all completely multiplicative sequences of successively greater length. At the top of the script, 'N' is the limit of the search, and 'limit' is the constraint on the sums. It prints out lists of primes where the sequence is <math>-1</math>.

<pre>
N = 300
limit = 2

# fisrt use Eratosthenes to find the primes up to N
# is_prime[n] = true iff n is prime
is_prime = [None, False] + [True]*(N-1)
p = 2
ok = True
while ok:
for i in range(2*p, N+1, p):
is_prime[i] = False
ok = (True in is_prime[p+1:])
if ok:
p = p+1 + is_prime[p+1:].index(True)

# make list of primes
primes = []
for i in range(1, N+1):
if is_prime[i]:
primes.append(i)
n_primes = len(primes)

# make list a[1..N] where a[n] is a dict with primes as keys and a[n][p] = True
# iff p|n an odd number of times
a = [None]
for n in range(1,N+1):
fact = {}
k = n
for p in primes:
v = False
while k % p == 0:
v = not v
k /= p
fact[p] = v
a.append(fact)

n_seqs = [1]
xx = [[[False]*n_primes, 1]] # 0th item = specification of primes for which x[p]=-1, 1st item = partial sum
c = 1
n = 2
while (n<=N) & (c>0):
print "first sequence:", [primes[i] for i in range(n_primes) if xx[0][0][i]]
new_xs = []
if is_prime[n]:
# ... fork
i = primes.index(n)
for x in xx:
seq = x[0]
tot = x[1]
new_seq = list(seq)
new_seq[i] = True
new_xs.append([new_seq, tot-1])
x[1] = tot+1
else:
# ... factorise
fact = a[n]
for x in xx:
seq = x[0]
v = 1
for i in range(n_primes):
if fact[primes[i]] & seq[i]:
v = -v
x[1] += v
# remove sequences with bad sums
xx = [x for x in xx+new_xs if abs(x[1])<=limit]
c = len(xx)
n_seqs.append(c)
print "\nn =", n
print "number of sequences =", c
n += 1
</pre>

Search for completely multiplicative sequences - Revision history

Alec: New page: This is a simple Python script to search for all completely multiplicative sequences of successively greater length. At the top of the script, 'N' is the limit of the search, and 'limit' i...