A Python program for finding weird numbers

Figured it out:

``````from itertools import takewhile
from math import floor
from time import time

start = time()

primitive_semiperfect_numbers = set()

n = 26531
multiples_lists = []
for possible_factor in range(2, floor(n**0.5) + 1):
multiples_list = set(possible_factor * i for i in range(1, n//possible_factor + 1))
multiples_lists.append(multiples_list)

def main():
global n
step = 2
if n > 10**21:
step = 1
weirdnumbers = [i for i in range(2, n, step) if isweird(i) == True]
print("First", len(weirdnumbers), "weird nos:\n", weirdnumbers)

def isweird(n):
global multiples_list
global primitive_semiperfect_numbers
factors = set()
possible_factor = 2
for i in multiples_lists:
if n in i:
if not (possible_factor in primitive_semiperfect_numbers or n//possible_factor in primitive_semiperfect_numbers):
factors = factors.union({possible_factor, n//possible_factor})
else:
return False
possible_factor = possible_factor + 1
if possible_factor == n:
break
difference = sum(factors) - n
if difference < 0:
return False
if difference == 0:
return False
factors = set(i for i in factors if i <= difference)
ns = n - (difference + n - sum(factors))
if ns < 0:
return True # n is weird
""" Code from Stefan2:
https://discuss.python.org/t/a-python-program-for-
finding-weird-numbers/48654/6 """
sums = 1
for d in factors:
sums |= sums << d
if not sums >> ns & 1:
return True
else:
return False
primitive_semiperfect_numbers.append(n)

main()

end = time()
print("Execution time: ", round(end - start, 2), "s")
``````

Though this is slower than my previous program below. They both have a max of 26531, but the above takes .29 s and the below .09 s.

``````""" Last updated 5/8/24 """

from itertools import combinations, takewhile
from math import prod
from time import time

start = time()

primitivesp_nos = {6} # No multiple of a semiperfect number is weird

def main(): # Range of nos [number1, number2]
max = 26531 # Below - calculates all weird numbers in range
step = 2
if max > 10**21: # No odd weird numbers below 10^21
step = 1
weird_nos = [i for i in range(2, max, step) if isweird(i) == 1]
print("First", len(weird_nos), "weird nos:\n", weird_nos)

def get_prime_fctrs(n): # Wheel factorization
""" Code from Jerome Richard """
""" stackoverflow.com/questions/70635382/
fastest-way-to-produce-a-list-of-all-divisors-of-a-number """
fctrs = [] # Empty list
if n % 6 == 0: # 6 is primitive semiperfect, equals 2 * 3
return "Semiperfect"
while n % 2 == 0: # Divides by 2 (adds 2, 2...) to prime fctrs
fctrs.append(2) # Append 2
n //= 2
t = 2 ** (len(fctrs) + 1) - 1 # Test
while n % 3 == 0: # Divides by 3 (adds 3, 3...) to prime fctrs
fctrs.append(3) # Append 3
n //= 3
i = 5
while i*i <= n: # Repeats above process
for k in (i, i+2):
while n % k == 0:
while k <= t:
""" 2^k * p is never weird """
return "Semiperfect"
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
prime_fctrs = get_prime_fctrs(n)
if prime_fctrs == "Semiperfect":
return 0
sum_fctrs = 1 # Sum of all factors based on formula
fctrs = set(prime_fctrs) # Set of all fctrs
for i in fctrs:
sum_fctrs = sum_fctrs * (i ** (prime_fctrs.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
return 0
if difference == 0: # If difference = 0, n is perfect
primitivesp_nos.add(n) # n is primitive semiperfect
return 0
for i in range(2, len(prime_fctrs)):
for j in combinations(prime_fctrs, i): # All combinations of prime fctrs
product = prod(j) # Product
if product not in primitivesp_nos: # Factor product added to set
else: # If factor is semiperfect, n cannot be weird
return 0
fctrs.add(1) # All numbers have 1 as a factor
fctrs = sorted(fctrs) # Sorts fctrs in order
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 """
prime_fctrs = 1 # Overwrites list, saves space
for d in fctrs:
prime_fctrs |= prime_fctrs << d
if not prime_fctrs >> ns & 1: # Checks if combos set contains ns
return 1
else:
return 0

main() # Start program

end = time()
print("Execution time: ", round(end - start, 2), "s")
``````

I think I might be missing something. Maybe the

`````` for i in multiples_lists:
if n in i:
if not (possible_factor in primitive_semiperfect_numbers or n//possible_factor in primitive_semiperfect_numbers):
factors = factors.union({possible_factor, n//possible_factor})
``````

can be converted to a listcomp? (If you like I can add labels to first program)