|
::<syntaxhighlight lang="python"># anySum :: Int -> [Int] -> [Int]
from itertools import combinations , takewhile▼""" Last updated 5/8/24 """
▲from itertools import combinations, takewhile
from math import prod
primitivesp_nos = set(); primes = []
primitivesp_nos = {6} # No multiple of a semiperfect number is weird
def main(): # Range of nos [number1, number2]
weird_nos = []
n = 50 # Find n weird numbers 1766
x = 1 # Number to be tested
while n > 0:
if isweird(x) == 1: weird_nos.append(x); n = n - 1
n = n - 1
x = x + 1
print("First", len(weird_nos), "weird nos:\n", weird_nos)
def isweird(n): # Checks if n is weird ▼def get_prime_fctrs(n): # Wheel factorization
global primes; global primitivesp_nos .add(; x = []; a = n ) ▼
""" Code from Jerome Richard """
""" stackoverflow.com/questions/70635382/
while na % ki == 0: x.append(i); a = a//i▼ fastest-way-to-produce-a-list-of-all-divisors-of-a-number """
fctrs = [] # Emptyif listi * i > a: break
▲ if a > 1: weird_nosx.append( xa)
while n % 2 == 0: # Divides by 2 (adds 2, 2...) to prime fctrs
if x == [n]: fctrsprimes.append(2n); #return Append 20
sum_fctrs = 1; fctrs n //= 2set(x)
for i in fctrs: sum_fctrs = sum_fctrs * (i ** (x.count(i) + 1) - 1)//(i - 1) ▼
while n % 3 == 0: # Divides by 3 (adds 3, 3...) to prime fctrs
difference = sum_fctrs - 2 * n
fctrs.append(3) # Append 3
if difference n //<= 30:
if difference == 0: primitivesp_nos.add(n) ▼
i = 5
while i*i <= n: # Repeats above process
for k in (i, i+2):
fctrs.append(k) # Append k
n //= k
i += 6
if n > 1:
fctrs.append(n) # Append n
return fctrs # Passes prime fctrs to isweird
▲def isweird(n): # Checks if n is weird
global primitivesp_nos # Retrieves list of primitive semiperfect nos
if n % 6 == 0: # 6 is primitive semiperfect, equals 2 * 3
return 0
x = get_prime_fctrs(n)
sum_fctrs = 1 # Sum of all factors based on formula
fctrs = set(x) # Set of all fctrs
▲ sum_fctrs = sum_fctrs * (i ** (x.count(i) + 1) - 1)//(i - 1)
difference = sum_fctrs - n - n # Difference between sum of fctrs and target n
if difference <= 0: # If difference < 0, n is deficient
if difference == 0:
return 0
for i in range(2, len(x)):
for j in combinations(x, i): # All combinations of prime fctrs
product = prod(j) # Product
if product not in primitivesp_nos: # Factor fctrs.add(product added to set )
else: return fctrs.add(product)0
x = 1; fctrs = {1}.union(set(i for i in fctrs if i <= difference))
else: # If factor is semiperfect, n cannot be weird
ns = n - (difference + n - sum(fctrs)) return 0
xif =ns 1< #0: Overwritesreturn list, saves space1
fctrs.add(1)for #d Allin numbersfctrs: havex 1|= asx a<< factord
fctrsif =not sorted(fctrs)x #>> Sortsns fctrs& in1: orderreturn 1
else: primitivesp_nos.add(n); return 0
fctrs = set(takewhile(lambda x:x <= difference, fctrs)) # Remaining fctrs set
ns = n - (difference + n - sum(fctrs)) # Stores in variable to save space
if ns < 0:
return 1 # n is weird
""" Code from Stefan2:
https://discuss.python.org/t/a-python-program-for-
finding-weird-numbers/48654/6 """
for d in fctrs:
x |= x << d
if not x >> ns & 1: # Checks if combos set contains ns
isweird = 1
else:
isweird = 0
return isweird
main() # Start program
end = time()
print("Execution time: ", round(end - start, 2), "s")
-- -> [100,96]</syntaxhighlight>
|