# A Python program for finding weird numbers

This is my first post!

I just got into programming a couple months ago. I created a program for finding weird numbers (see Weird number - Wikipedia).

It takes about 0.3 s for first 50 weird numbers.

If you have any questions about how it works or suggestions (such as if this is in the wrong place), let me know!

``````from itertools import combinations
from sympy import divisors
from time import time

start = time()

def main(): # Range of numbers [number1, number2]
min = 1
max = 26531 # below - Contains only weird numbers in range
even = [i for i in range(min + min % 2, max, 2) if (i % 3 != 0 and isweird(i) == 1)] # No multiple of 20 is weird
print("Even weird no:\n", even)
if max > 10**21: # No odd weird numbers below 10^21
if min < 10**21:
min = int(10**21 + 1)
odd = [i for i in range(min + min % 2 - 1, max, 2) if isweird(i) == i]
print("Odd weird no: ", odd)

def isweird(n): # Filters nonweird numbers
factors = divisors(n)
factors.remove(n) # Creates list of factors of n, excluding n
difference = sum(factors) - n
if difference <= 0: # If n is deficient or perfect, system exits
return
sum_factors = 0
factors.reverse()
for i in factors: # Checks for obvious nonweird
new = sum_factors + i # Stores new sum_factors in variable to save time
if new < n:
sum_factors = new
elif new == n:
return
included_factors = set(StopIteration if i <= difference else i for i in factors if i > difference) # Checks for factors that must be in combo that sums to n
factors = [i for i in factors if i not in included_factors]
newsum = n - sum(included_factors) # New sum
for i in range(len(factors) - (n % 2) * ((n - sum(included_factors) - len(factors)) % 2),  1, -(n % 2 + 1)): # Combos that sum to n
for j in combinations(factors, i):
if sum(j) == newsum:
return
return 1 # Weird n is passed back to main

main()

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

Cyrus Polentschz

Below: nothing in particular - just wanted to share this program. It was moved to Python Help by a moderator.

1 Like

itâs fixed

(Small nitpick: Your Wikipedia link includes the dot - for future examples, try having the dot outside the parentheses, or explicitly create your link with the `[example link text](https://link.destination.example/)` notation. For anyone whoâs looking for the correct link, itâs here.)

The key here is the factors of the number. While itâs possible to test if a single number is weird, doing this for a large group of numbers (eg to find âthe first N weird numbersâ) should be able to take advantage of the repetition. In your example here, you query the divisors of each number completely independently; but you also have a min and max. So Iâd start like this:

``````factors = defaultdict(list)
for factor in range(2, max):
for multiple in range(factor + factor, max, factor):
factors[multiple].append(factor)
``````

There! Now you have all of those factors ready to go. You can then index into that instead of using divisors(), and it should be way WAY faster. (Note that this will not include self - for example, factors[12] is [2,3,4,6] without including 12. You could have it include that, but you were removing n itself, so itâs easier to just not include it in the first place. To change that behaviour, replace the âfactor + factorâ with just âfactorâ.)

``````included_factors = set(StopIteration if i <= difference else i for i in factors if i > difference)
``````

StopIteration is just another value here. Since this is a set, youâll only have one of that value, but it wonât halt the search. But I would also expect that it would bomb when you try to take that sum, which seems odd, since you didnât mention that.

Hopefully thatâll help out a bit! Lemme know if thereâs anything in particular youâre interested in here.

Thank you! I agree with your first suggestion about the dict. The line with the included_factors, the sum actually does work - when you run the program for, say, min = 1 and max = 10000 it actually does generate all 7 weird numbers in that range correctly.

For 10000 it returns:

``````Even weird no:
[70, 836, 4030, 5830, 7192, 7912, 9272]
``````

which are the correct numbers that it should yield.

Nice little exercise. Hereâs mine, also takes ~0.3 seconds. Will read yours next:

``````from sympy import divisors
from time import time

start = time()

def main():
show = 50
n = 0
while show:
n += 1
D = divisors(n)[:-1]
if sum(D) > n:
sums = 1
for d in D:
sums |= sums << d
if not sums >> n & 1:
print(n)
show -= 1

main()

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

Attempt This Online!

Curious. Maybe itâs just never actually tripping. I didnât delve too deep into it.

Yeah, thatâs weird. The goal of that line was to search for factors that must be included in a combo for it to sum to n (in which case n isnât weird.) If a specific factor is greater than the difference between sum(n), the sum of all factors of n except itself, and n, it must be included because the maximum possible sum of a factor combo if it were excluded would be sum(n) minus that factor, which is less than n.

My code

Updated program (replaced the line with the âStopIterationâ). Still need to replace the sympy.divisors as Rosuav suggested. Itâs faster than the original, which took â 5 s for range 1 to 100000. This one takes 3. Plus for 1 to 300000, the original took 15 s, but this one takes 7 s.

``````from itertools import combinations, takewhile
from sympy import divisors
from time import time

start = time()

def main(): # Range of numbers [number1, number2]
min = 1
max = 300000 # below - Contains only weird numbers in range
weird_numbers = [i for i in range(min + min % 2, max, 2) if (i % 3 != 0 and isweird(i) == 1)] # No multiple of 6 is weird
if max > 10**21: # No odd weird numbers below 10^21
weird_numbers += [i for i in range(min + min % 2 - 1, max, 2) if isweird(i) == i]
weird_numbers = sorted(weird_numbers)
print("Weird numbers:\n", weird_numbers)

def isweird(n): # Filters nonweird numbers
factors = divisors(n)
factors.remove(n) # Creates list of factors of n, excluding n
difference = sum(factors) - n
if difference <= 0: # If n is deficient or perfect, system exits
return
sum_factors = 0
factors.reverse()
for i in factors: # Checks for obvious nonweird
new = sum_factors + i # Stores new sum_factors in variable to save time
if new < n:
sum_factors = new
elif new == n:
return
included_factors = set(takewhile(lambda x:x > difference, factors)) # Checks for factors that must be in combo that sums to n
factors = set(factors) - included_factors
newsum = n - sum(included_factors) # New sum
for i in range(len(factors) - (n % 2) * ((n - sum(included_factors) - len(factors)) % 2),  1, -(n % 2 + 1)): # Combos that sum to n
for j in combinations(factors, i):
if sum(j) == newsum:
return
return 1 # Weird n is passed back to main

main()

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

``````

Can you explain what these lines do? In your Attempt this Online code.

``````            sums = 1
for d in D:
sums |= sums << d
if not sums >> n & 1:
print(n)
show -= 1
``````

My `sums` is a bitset. Bit i means number i. For example `sums = 33` would represent the set `{0, 5}`. Each new `d` can be added to each previous sum, and `sums << d` represents those new sums. And `sums >> n & 1` checks whether the set of sums contains the sum n.

In other words, itâs equivalent to this:

``````            sums = {0}
for d in D:
sums |= {sum + d for sum in sums}
if n not in sums:
print(n)
show -= 1
``````

Improved program (using some of Stefan2âs and Rosuavâs advice/responses). Itâs longer but faster. You have to input the upper limit. The program finds all weird numbers between 1 and the upper limit.

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

from itertools import combinations, takewhile
from math import prod

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

def main(): # Range of nos [number1, number2]
print("This program prints all weird numbers between 1 and n.")
max = int(input("Enter n, the upper limit: "))
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 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 combos 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 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
``````

Can you please explain how calculating the first N weird numbers dependently rather than independently saves time and what this does? I understand the idea overall just not all the specific Python tools.

``````factors = defaultdict(list)
for factor in range(2, max):
for multiple in range(factor + factor, max, factor):
factors[multiple].append(factor)
``````

Thank you!

This part is just looking at factors. The reason itâs faster is that, to compute the factors of N, you need only check the prime numbers up to its square root; and, in fact, you can extremely efficiently list all of the factors of a number by working upwards rather than downwards.

That is to say: Instead of computing the factors of N, we actually enumerate the multiples of every number up to the maximum. So we look at 2, and mark off every even number as having 2 as a factor; then look at 3, and mark off all multiples of three; and so on.

This is being done with a minimum of arithmetic - potentially just addition, not even multiplication, and certainly no expensive division or square rooting. The downside is that the entire collection has to be kept in memory.

Sounds like a good idea. So what you do is, for each number, you create a list of its multiples, then for each number you are testing you check which of these lists it belongs in?

Pretty much. The lists are indexed by the multiple, so itâs easy to pick up all of the factors of a number, but basically what you said, yeah.

and you only need to create those lists of multiples for prime numbers at or below the square root of maximum?

Actually that part is kinda inverted. Instead of building those lists up to the square root, you build them all the way to the number; but there wonât be any NEW factors after the square root.

But you only create lists of multiples for primes (i.e. 2, 3, 5, etc.), not 4 or 6?

Edit: missing an `primitivesp_nos.add(n)` after

``````if not prime_fctrs >> ns & 1: # Checks if combos set contains ns
return 1
else:
``````