We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?


In [1]:
def prime_factors(n): # from eratosthenes
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        
        d = d + 1
        if d * d > n:
            if n > 1:
                factors.append(n)
            break
            
    return factors

def primes_less_than_n(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

max_num_digits = 7
all_primes = primes_less_than_n((10**max_num_digits+1)-1)
max_p = all_primes[-1]
all_primes = set(all_primes)
print len(all_primes)

def is_prime(n):
    if n <= max_p:
        return n in all_primes
    
    return len(prime_factors(n)) == 1


664579

Misc number theory fact: if 3 | sum of digits of N then 3 | N.

For 4: 10 = 2x5

For 5: 15 = 3x5

For 6: 21 = 3x7

For 7: 28 = 227

For 8: 36 = 223*3

For 9: 45 = 335

So we only need to try 4 and 7 digit numbers.


In [2]:
import itertools
for n in [4,7]:
    if n == 5 or n == 6:
        continue
        
    d = range(1,n+1)
    for p in itertools.permutations(d):
        if p[-1] % 2 == 0 or p[-1] == 5:
            continue
            
        pt = int("".join([str(i) for i in p]))
        if is_prime(pt):
            print 'n:',n,'p:',pt


n: 4 p: 1423
n: 4 p: 2143
n: 4 p: 2341
n: 4 p: 4231
n: 7 p: 1234657
n: 7 p: 1245763
n: 7 p: 1246537
n: 7 p: 1246573
n: 7 p: 1247563
n: 7 p: 1254367
n: 7 p: 1254637
n: 7 p: 1256347
n: 7 p: 1257463
n: 7 p: 1263547
n: 7 p: 1264537
n: 7 p: 1264573
n: 7 p: 1265347
n: 7 p: 1275643
n: 7 p: 1276543
n: 7 p: 1324567
n: 7 p: 1342567
n: 7 p: 1342657
n: 7 p: 1345627
n: 7 p: 1354267
n: 7 p: 1356247
n: 7 p: 1356427
n: 7 p: 1362457
n: 7 p: 1425367
n: 7 p: 1426753
n: 7 p: 1427563
n: 7 p: 1427653
n: 7 p: 1435627
n: 7 p: 1436257
n: 7 p: 1436527
n: 7 p: 1452637
n: 7 p: 1453267
n: 7 p: 1463257
n: 7 p: 1465273
n: 7 p: 1476253
n: 7 p: 1476523
n: 7 p: 1524637
n: 7 p: 1524763
n: 7 p: 1532647
n: 7 p: 1546273
n: 7 p: 1546327
n: 7 p: 1562347
n: 7 p: 1563427
n: 7 p: 1564237
n: 7 p: 1572643
n: 7 p: 1574623
n: 7 p: 1576243
n: 7 p: 1624573
n: 7 p: 1625347
n: 7 p: 1632457
n: 7 p: 1634257
n: 7 p: 1645327
n: 7 p: 1647253
n: 7 p: 1647523
n: 7 p: 1652347
n: 7 p: 1653427
n: 7 p: 1672453
n: 7 p: 1674523
n: 7 p: 1725463
n: 7 p: 1726453
n: 7 p: 1742563
n: 7 p: 1752643
n: 7 p: 1764253
n: 7 p: 2136457
n: 7 p: 2143567
n: 7 p: 2145763
n: 7 p: 2146357
n: 7 p: 2153647
n: 7 p: 2156437
n: 7 p: 2163547
n: 7 p: 2176543
n: 7 p: 2315647
n: 7 p: 2341567
n: 7 p: 2345617
n: 7 p: 2347561
n: 7 p: 2354167
n: 7 p: 2364517
n: 7 p: 2365471
n: 7 p: 2375641
n: 7 p: 2376541
n: 7 p: 2413657
n: 7 p: 2431657
n: 7 p: 2436517
n: 7 p: 2436571
n: 7 p: 2451367
n: 7 p: 2451637
n: 7 p: 2456371
n: 7 p: 2456731
n: 7 p: 2457361
n: 7 p: 2457613
n: 7 p: 2467351
n: 7 p: 2475163
n: 7 p: 2476351
n: 7 p: 2516473
n: 7 p: 2534671
n: 7 p: 2536147
n: 7 p: 2537461
n: 7 p: 2543617
n: 7 p: 2546317
n: 7 p: 2547361
n: 7 p: 2547613
n: 7 p: 2547631
n: 7 p: 2561743
n: 7 p: 2563147
n: 7 p: 2563417
n: 7 p: 2576341
n: 7 p: 2613547
n: 7 p: 2631457
n: 7 p: 2634517
n: 7 p: 2637451
n: 7 p: 2637541
n: 7 p: 2641357
n: 7 p: 2645371
n: 7 p: 2647531
n: 7 p: 2651437
n: 7 p: 2651743
n: 7 p: 2653741
n: 7 p: 2654317
n: 7 p: 2654371
n: 7 p: 2657143
n: 7 p: 2657341
n: 7 p: 2674513
n: 7 p: 2674531
n: 7 p: 2714563
n: 7 p: 2716453
n: 7 p: 2716543
n: 7 p: 2734561
n: 7 p: 2735641
n: 7 p: 2736451
n: 7 p: 2741653
n: 7 p: 2743561
n: 7 p: 2745361
n: 7 p: 2754361
n: 7 p: 2761453
n: 7 p: 2761543
n: 7 p: 2765143
n: 7 p: 3124567
n: 7 p: 3124657
n: 7 p: 3126457
n: 7 p: 3126547
n: 7 p: 3145627
n: 7 p: 3152467
n: 7 p: 3154267
n: 7 p: 3156427
n: 7 p: 3165427
n: 7 p: 3214567
n: 7 p: 3214657
n: 7 p: 3215467
n: 7 p: 3216457
n: 7 p: 3241657
n: 7 p: 3245761
n: 7 p: 3246157
n: 7 p: 3246751
n: 7 p: 3251467
n: 7 p: 3254761
n: 7 p: 3256417
n: 7 p: 3256471
n: 7 p: 3257641
n: 7 p: 3261547
n: 7 p: 3264571
n: 7 p: 3265741
n: 7 p: 3412567
n: 7 p: 3412657
n: 7 p: 3415627
n: 7 p: 3421567
n: 7 p: 3421657
n: 7 p: 3427561
n: 7 p: 3451627
n: 7 p: 3452671
n: 7 p: 3456127
n: 7 p: 3456217
n: 7 p: 3456721
n: 7 p: 3457261
n: 7 p: 3461257
n: 7 p: 3462517
n: 7 p: 3462751
n: 7 p: 3465271
n: 7 p: 3467251
n: 7 p: 3467521
n: 7 p: 3475261
n: 7 p: 3512647
n: 7 p: 3514267
n: 7 p: 3516427
n: 7 p: 3524617
n: 7 p: 3526147
n: 7 p: 3526741
n: 7 p: 3542167
n: 7 p: 3542761
n: 7 p: 3546271
n: 7 p: 3546721
n: 7 p: 3561247
n: 7 p: 3562417
n: 7 p: 3574621
n: 7 p: 3576421
n: 7 p: 3612457
n: 7 p: 3612547
n: 7 p: 3624157
n: 7 p: 3627451
n: 7 p: 3642157
n: 7 p: 3642571
n: 7 p: 3672451
n: 7 p: 3672541
n: 7 p: 3674521
n: 7 p: 3675241
n: 7 p: 3725461
n: 7 p: 3742561
n: 7 p: 3746521
n: 7 p: 3752641
n: 7 p: 3756241
n: 7 p: 3756421
n: 7 p: 3765241
n: 7 p: 4125637
n: 7 p: 4125673
n: 7 p: 4126537
n: 7 p: 4127653
n: 7 p: 4135627
n: 7 p: 4152763
n: 7 p: 4157623
n: 7 p: 4165327
n: 7 p: 4167523
n: 7 p: 4172653
n: 7 p: 4175263
n: 7 p: 4176253
n: 7 p: 4213567
n: 7 p: 4216573
n: 7 p: 4216753
n: 7 p: 4231567
n: 7 p: 4235761
n: 7 p: 4253167
n: 7 p: 4253617
n: 7 p: 4253671
n: 7 p: 4257163
n: 7 p: 4257613
n: 7 p: 4261357
n: 7 p: 4263157
n: 7 p: 4265137
n: 7 p: 4265713
n: 7 p: 4265731
n: 7 p: 4267531
n: 7 p: 4271563
n: 7 p: 4276513
n: 7 p: 4312657
n: 7 p: 4321657
n: 7 p: 4325617
n: 7 p: 4326571
n: 7 p: 4356217
n: 7 p: 4356721
n: 7 p: 4361257
n: 7 p: 4362751
n: 7 p: 4365271
n: 7 p: 4372651
n: 7 p: 4375621
n: 7 p: 4513627
n: 7 p: 4516327
n: 7 p: 4521367
n: 7 p: 4521637
n: 7 p: 4523671
n: 7 p: 4526371
n: 7 p: 4527361
n: 7 p: 4537261
n: 7 p: 4561237
n: 7 p: 4561327
n: 7 p: 4561723
n: 7 p: 4562317
n: 7 p: 4562731
n: 7 p: 4563127
n: 7 p: 4563217
n: 7 p: 4563271
n: 7 p: 4567231
n: 7 p: 4571263
n: 7 p: 4572163
n: 7 p: 4621537
n: 7 p: 4625713
n: 7 p: 4631527
n: 7 p: 4637251
n: 7 p: 4652173
n: 7 p: 4652317
n: 7 p: 4657123
n: 7 p: 4657321
n: 7 p: 4672531
n: 7 p: 4675123
n: 7 p: 4712563
n: 7 p: 4716253
n: 7 p: 4721653
n: 7 p: 4723561
n: 7 p: 4725613
n: 7 p: 4725631
n: 7 p: 4732561
n: 7 p: 4752361
n: 7 p: 4765213
n: 7 p: 5123467
n: 7 p: 5126347
n: 7 p: 5126437
n: 7 p: 5136427
n: 7 p: 5142637
n: 7 p: 5143267
n: 7 p: 5146237
n: 7 p: 5162473
n: 7 p: 5162743
n: 7 p: 5164273
n: 7 p: 5164723
n: 7 p: 5172463
n: 7 p: 5176243
n: 7 p: 5214367
n: 7 p: 5214637
n: 7 p: 5214763
n: 7 p: 5216473
n: 7 p: 5231647
n: 7 p: 5234167
n: 7 p: 5236741
n: 7 p: 5237641
n: 7 p: 5241673
n: 7 p: 5243167
n: 7 p: 5243761
n: 7 p: 5246173
n: 7 p: 5246713
n: 7 p: 5247163
n: 7 p: 5261743
n: 7 p: 5263417
n: 7 p: 5264137
n: 7 p: 5264173
n: 7 p: 5267341
n: 7 p: 5267413
n: 7 p: 5271463
n: 7 p: 5274163
n: 7 p: 5274631
n: 7 p: 5276431
n: 7 p: 5312467
n: 7 p: 5321467
n: 7 p: 5321647
n: 7 p: 5327461
n: 7 p: 5341627
n: 7 p: 5342167
n: 7 p: 5342761
n: 7 p: 5346127
n: 7 p: 5347621
n: 7 p: 5361247
n: 7 p: 5364127
n: 7 p: 5367421
n: 7 p: 5376421
n: 7 p: 5421673
n: 7 p: 5421763
n: 7 p: 5423167
n: 7 p: 5423617
n: 7 p: 5426173
n: 7 p: 5426371
n: 7 p: 5426713
n: 7 p: 5431627
n: 7 p: 5436127
n: 7 p: 5436217
n: 7 p: 5436271
n: 7 p: 5436721
n: 7 p: 5461273
n: 7 p: 5461723
n: 7 p: 5462137
n: 7 p: 5462173
n: 7 p: 5463217
n: 7 p: 5463721
n: 7 p: 5472613
n: 7 p: 5472631
n: 7 p: 5473261
n: 7 p: 5476213
n: 7 p: 5614327
n: 7 p: 5621437
n: 7 p: 5624137
n: 7 p: 5624317
n: 7 p: 5624713
n: 7 p: 5627143
n: 7 p: 5631427
n: 7 p: 5632741
n: 7 p: 5634217
n: 7 p: 5634721
n: 7 p: 5641327
n: 7 p: 5643217
n: 7 p: 5647231
n: 7 p: 5647321
n: 7 p: 5672341
n: 7 p: 5672413
n: 7 p: 5674231
n: 7 p: 5723461
n: 7 p: 5724163
n: 7 p: 5724613
n: 7 p: 5726143
n: 7 p: 5726341
n: 7 p: 5734621
n: 7 p: 5742361
n: 7 p: 5742631
n: 7 p: 5746123
n: 7 p: 5746231
n: 7 p: 5761423
n: 7 p: 5762143
n: 7 p: 5762413
n: 7 p: 5763421
n: 7 p: 6124753
n: 7 p: 6134257
n: 7 p: 6142573
n: 7 p: 6145273
n: 7 p: 6145327
n: 7 p: 6145723
n: 7 p: 6152743
n: 7 p: 6154273
n: 7 p: 6154723
n: 7 p: 6174253
n: 7 p: 6175243
n: 7 p: 6175423
n: 7 p: 6214357
n: 7 p: 6214573
n: 7 p: 6214753
n: 7 p: 6215347
n: 7 p: 6217543
n: 7 p: 6234517
n: 7 p: 6235147
n: 7 p: 6235417
n: 7 p: 6235741
n: 7 p: 6241537
n: 7 p: 6243157
n: 7 p: 6245731
n: 7 p: 6251347
n: 7 p: 6251743
n: 7 p: 6257143
n: 7 p: 6257431
n: 7 p: 6274531
n: 7 p: 6275341
n: 7 p: 6312547
n: 7 p: 6321457
n: 7 p: 6325471
n: 7 p: 6342157
n: 7 p: 6342517
n: 7 p: 6345127
n: 7 p: 6345271
n: 7 p: 6345721
n: 7 p: 6347521
n: 7 p: 6352147
n: 7 p: 6352741
n: 7 p: 6354217
n: 7 p: 6415237
n: 7 p: 6421573
n: 7 p: 6423517
n: 7 p: 6423751
n: 7 p: 6435127
n: 7 p: 6435721
n: 7 p: 6437521
n: 7 p: 6451723
n: 7 p: 6452137
n: 7 p: 6453721
n: 7 p: 6457123
n: 7 p: 6472351
n: 7 p: 6472513
n: 7 p: 6473251
n: 7 p: 6475321
n: 7 p: 6512347
n: 7 p: 6512437
n: 7 p: 6513427
n: 7 p: 6514327
n: 7 p: 6524137
n: 7 p: 6527413
n: 7 p: 6541723
n: 7 p: 6542713
n: 7 p: 6543127
n: 7 p: 6547213
n: 7 p: 6572143
n: 7 p: 6572413
n: 7 p: 6572431
n: 7 p: 6574231
n: 7 p: 6714523
n: 7 p: 6724351
n: 7 p: 6725143
n: 7 p: 6732541
n: 7 p: 6734521
n: 7 p: 6745231
n: 7 p: 6751243
n: 7 p: 6754213
n: 7 p: 7124653
n: 7 p: 7125463
n: 7 p: 7126453
n: 7 p: 7126543
n: 7 p: 7142563
n: 7 p: 7145623
n: 7 p: 7152643
n: 7 p: 7164253
n: 7 p: 7165423
n: 7 p: 7215643
n: 7 p: 7216453
n: 7 p: 7216543
n: 7 p: 7234651
n: 7 p: 7245361
n: 7 p: 7246513
n: 7 p: 7253461
n: 7 p: 7253641
n: 7 p: 7256341
n: 7 p: 7264351
n: 7 p: 7264513
n: 7 p: 7264531
n: 7 p: 7324561
n: 7 p: 7324651
n: 7 p: 7352461
n: 7 p: 7354261
n: 7 p: 7356421
n: 7 p: 7362541
n: 7 p: 7412563
n: 7 p: 7412653
n: 7 p: 7415623
n: 7 p: 7421563
n: 7 p: 7425361
n: 7 p: 7425631
n: 7 p: 7426351
n: 7 p: 7432651
n: 7 p: 7435621
n: 7 p: 7451263
n: 7 p: 7451623
n: 7 p: 7452163
n: 7 p: 7456231
n: 7 p: 7456321
n: 7 p: 7462513
n: 7 p: 7514623
n: 7 p: 7524631
n: 7 p: 7526143
n: 7 p: 7536241
n: 7 p: 7536421
n: 7 p: 7541623
n: 7 p: 7542163
n: 7 p: 7546321
n: 7 p: 7561423
n: 7 p: 7562341
n: 7 p: 7562413
n: 7 p: 7562431
n: 7 p: 7564231
n: 7 p: 7621543
n: 7 p: 7624531
n: 7 p: 7625143
n: 7 p: 7625341
n: 7 p: 7641253
n: 7 p: 7642513
n: 7 p: 7652413

In [ ]: