Talk:Weird numbers: Difference between revisions
Content deleted Content added
→A faster and less ambitious algorithm ?: Added a Haskell version of an anySum (for testing) |
No edit summary |
||
Line 1:
=== My version. ===
I saw there's already a Python program listed here for doing this, but I (with help from some others) created this one. Using the "sum of factors" formula it tests if a number is abundant BEFORE generating the list of each factors. If the number is deficient, the program returns so and saves memory. The program is alnmost twice as fast as the original, taking 0.16 s for the first 50.
::<lang python># anySum :: Int -> [Int] -> [Int]
""" 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]
weird_nos = []
n = 50 # Find n weird numbers
x = 1 # Number to be tested
while n > 0:
if isweird(x) == 1:
weird_nos.append(x)
n = n - 1
x = x + 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
fctrs.add(product)
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:
primitivesp_nos.add(n)
return 0
main() # Start program
end = time()
print("Execution time: ", round(end - start, 2), "s")
-- -> [100,96]</lang>
===A faster and less ambitious algorithm ?===
| |||