fork download
copy 
  1. from itertools import accumulate, chain, cycle, groupby, product, combinations
  2. from random import randrange
  3.  
  4. _small_primes = set((2, 3, 5, 7, 11, 13, 17, 19, 23))
  5.  
  6. def powerset(iterable):
  7.     "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
  8.     s = list(iterable)
  9.     return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
  10.  
  11. def td_factors(n):
  12.     fs = []
  13.     for f in accumulate(chain((2, 1, 2, 2), cycle((4, 2, 4, 2, 4, 6, 2, 6)))):
  14.         if f * f > n:
  15.             break
  16.         if not n % f:
  17.             fs.append(f)
  18.             n //= f
  19.             while not n % f:
  20.                 fs.append(f)
  21.                 n //= f
  22.             if is_prime(n):
  23.                 break
  24.     if n > 1:
  25.         fs.append(n)
  26.     return fs
  27.  
  28. def is_prime(n, k=25):
  29.     """ Miller-Rabin
  30.         returns: True if n is probably prime
  31.                     False if n is composite
  32.         k: number of random trial used
  33.     """
  34.     n = abs(n)
  35.     if n < 29:
  36.         return n in _small_primes
  37.     for pi in _small_primes:
  38.         if not n % pi:
  39.             return False
  40.     if pow(2, n-1, n) != 1:
  41.         return False
  42.     d, s = n - 1, 0
  43.     while not d % 2:
  44.         d //= 2
  45.         s += 1
  46.  
  47.     def is_spsp(n, a):
  48.         t = pow(a, d, n)
  49.         if t in (1, n-1):
  50.             return True
  51.         for _ in range(s-1):
  52.             t = (t * t) % n
  53.             if t == n - 1:
  54.                 return True
  55.             if t == 1:
  56.                 return False
  57.         return False
  58.     return all(is_spsp(n, randrange(2, n-1)) for _ in range(k))
  59.  
  60. n = 0
  61. while 1:
  62.     n += 1
  63.     tri = (n + 1) * n // 2
  64.     fac = td_factors(tri)
  65.     if len(set(powerset(fac))) > 500:
  66.         print("Euler12", tri)
  67.         break
  68.  
Success #stdin #stdout 1.31s 37064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Euler12 76576500
https://ideone.com/3AumOg
language:
Python 3 nbc (python 3.7.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!