Weird numbers: Difference between revisions
Content deleted Content added
No edit summary |
No edit summary |
||
Line 2,384: | Line 2,384: | ||
Approx computation time: 284 ms</pre> |
Approx computation time: 284 ms</pre> |
||
Edit: I experimented a bit and created this second version. It's faster than the original, takes about 0.16 s for first 50. See link below: |
|||
===My version=== |
===My version=== |
||
[https://ato.pxeger.com/run?1=hVfbjts2EH0X0H8YOEgh71qW1951F8Z6gSDNBi2KNsgW6EPaBrRErRlLpCJSe-nlS_qSl_aj-jWdIamb7aB-MCRyOByeOXM4-uuf8slslfz06e_aZNHlv1-8Ho1G8B3TBuoyZYancBFfxvNzoPEgyCpVgDC8MkrlGkRRqspAooqNkMwIJfUEDNvxh63IubMumNk2hmWlUjdqRMGbUXoOAm0YPq_tWzgOgrIShTDinuvyvVQaZ35f_gnP4HsFRZ0bUeYcVAYMNC9EyauMJwZkXWx4BULDAxdVGgQpzzACIcPxCte-ZfLOriKH75zx2cSvmv8SAP7sQr_jOzck8fFihutvhEzxzZr4VRqsySOanFF0LgCjYMPBcI0IOq8ECC69htnKDtBPZBipdRY-jmGNHrq5QShTVpZcktVgnuKSEMFZO0phPMIphuJ_dgahlCYc3YhKm9EEci7D1vV4AiN_HqVXP0uc7-YcfnfcvKds8PdZYiodSovlT1vOc8hYYlQlfrPJd7sRU16qlINN9Lcc_zm8FcmW4SY42RphxpOdusfU5ephiiSKP9aIGLEo_mq2XFwsLuextc6QkDgTPbCnyKiIaFQnPGJRLnBUZRHL8ygV90KrStv3yDOh2c9GbjOKob8qSvMEtDbwaZDwHJaUgRkdbUkEavnXJ9gE-MeaIfPncAILaHGvuKkrCaPbznQEg8Q_xyWN_68x0pRr2DzhYMjSFP1NYD6dTsfEHIu1j7jdwb42PJiP0csL-4weWhsJcbyGuX2nUsIgTyCkdNvVYyLGmPiCq39EPPcjXByLcOEjXExgcSTC4wEuegEu9gP0A4KqqheBOBFwhYS2hcpLzowGtkF-kGwkXPfBUBXsQEgIxQTE6Xy8VzftiXbuRIPZzmJH-5nD2Yag8193mOaS2CA58tQXvpXCY2uOseDAcIDTrofT7sDUwdWNCzhdw7Lj7HVfMAZ-Zc-v9Crgo3O8egZvmNZcD8iGmfV6BK7yG3VyFf9yy5Oddls3Cutc3-Vqw3LYl2zKo6kEQqdttZHyHi0r0p5GqRqZQXYcCk9z9oHdeoj4ar8qZy5IXRetZ6qA27qwF0jeqBjSnWm88VDIkGB4ybCBdGhuwt6-hPAtN62LthiInILIaYe6aPr7d89YoMKWac81amGNgi26gh3HMZrRg3WXiizjFZcJH_iKKNf0RwXcWmy4eeBckh0F60wZEgMvXEQYvGwjqj23V04HvtkfnLjcIzlEIrg0BxI4O-KsUZWht3XrrWFB62uPSFMUIEdp-Vll_kwgbTIquvrDubv9-mlEag905QNZ9zuavjWqjS2FF5jxvk3D7H1RdIeh24r0mJ7CD3SON35sYGh57calMhTGHg60842lamuIyCBjsXCRnYei5DUB0fP2w_6B55r7vLgKIHQHtx0iwSQFg91Mr977vyHc7YZnYw9T0yZtGSbsDBhyz-82rC7sBHkadqWF79rPIhKqSlF_D-qx7TXDnBWblMHj6pFEvaPZBHyarRpRKyjknffRYia176TCHj9P7QhWTdh5uMWwuQ3onlWCbfASIezpaLpkCW-1WdsK2ufkWUNh153SzLBbujU8Y3LuFm6NKfUqjlOhk1rrqevVp6q6i03MIvdKzdBdxYoIuRs5fLBJxTNGdg_fB-n4_HJ5cR4vu8trKLUU2Q94xT1U2N07tZ7Yc-newag80iPK1nf1x3rwenUFaQuKMoO562vC6Uu8xAaXC9WVcslJlDSYMU12B1gGLYX_RzeOK0PgPgtsUpn7NiEc8eajS7P5DoHAN8-vHnlS2yaXJlaAfXKFKp2GZB2B_XrBHo7aaT0aB-57yn9WNZ9X_wE] |
|||
Edit: I experimented a bit and created this second version. It's faster than the original, takes about 0.16 s for first 50. |
|||
::<syntaxhighlight 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]</syntaxhighlight> |
|||
=={{header|Quackery}}== |
=={{header|Quackery}}== |