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”.)

I am a bit curious about this line.

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 more about the calculating factors dependently part? Thanks!