shortest solution to 41 problems from Euler’s project
Hey! Today we will solve the 41st problem from Euler’s Project. We will do this first in expanded form, and then we will shorten the solution as much as possible.
Condition
We will consider an n-digit number to be pan-digital if each of the digits from 1 to n is used exactly once in it. For example, 2143 is a 4-digit pan-digital number and also a prime number. What is the largest n-digit pan-numeric prime?
Solution
First, let’s import the math module. From this we need the ceil () function, which rounds the number up.
import mathAs it is not difficult to guess from the condition, we need a function that determines whether the number is prime. Let’s write it.
def is_prime(x: int):
if x % 2 == 0:
return x == 2
for i in range(3, math.ceil(x ** 0.5), 2):
if x % i == 0:
return False
return True 2 is the only even prime number, so if the number turned out to be even, you need to check if it is not 2. If 2 – return True, otherwise – False. Since return exits the function, after it we are sure that the number is not even. We will check the divisors of x starting from 3 up to the rounded square root of x with a step of 2 (only odd ones). If x is divided entirely by one of the options, we immediately return False, since the number will not be prime. If no check resulted in an exit from the loop, then the number is prime.
Now let’s go directly to our problem. Determine the upper bound for the desired number: the maximum pan-digital number is 987_654_321 (yes, in Python, you can use the underscore as a separator in numbers). Since we need to find the maximum pan-digital prime number, we should move down from the maximum value and return the first suitable one. It is possible to write a function to determine if a number is pan-numeric and test only those numbers for simplicity, but this is highly inefficient. Of the nine-digit pan-digital numbers, only 9 will be! = 362_880, i.e. every 2_756th. As we can see, pan-digital numbers come across extremely rarely, so it is worth coming up with an algorithm that will generate only pan-digital numbers.
To generate all permutations, the itertools standard library has a special generator – permutations (). It accepts any iterable object (string / list / …) as input, and returns all permutations (each in the form of a list) of the given object.
Since we need to get the permutations from the largest to the smallest, we should indicate from the generator input in the reverse order. For example, for a nine-digit number, this would be [9, 8, 7, 6, 5, 4, 3, 2, 1]… To summarize: for an i-digit number, we need to make a list from i to 1:
list(range(i, 0, -1))We need to consider not only 9-digit numbers, but also 8/7/6/5/4/3/2/1-digit ones. Let’s check it out. We will also pass the converted list as an argument to the generator, where we change the type of each element to str. Since j is the value of a particular permutation, – will be a list of separate strings, each of which will be equivalent to a certain digit, we convert this value to a number. Then it remains to check it for simplicity, deduce it, if it is, and exit 2 loops. Let’s format this into a function:
def main():
for i in list(range(9, 0, -1)):
for j in itertools.permutations(list(map(str, list(range(i, 0, -1))))):
x = int(''.join(j))
if is_prime(x):
print(x)
returnNow let’s think a little more. Indeed, in a 9-digit pan-digital number, the sum of the digits s = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45, and 45 is divisible by 3. And, as we remember, if the sum of the digits of the number is divisible by 3, then the number itself is divisible by 3, respectively, it is not simple. It follows from this that none of the 9-digit pan-numeric numbers are prime. Similar manipulations for 2/3/5/6/8-digit pan-digital numbers will lead us to the conclusion that there are no simple ones among them either, since the sums of their digits are, respectively, 3, 6, 15, 21, 36. The only thing the same 1-digit pan-digital number – 1, – is not not simple, not complicated; but only the first part of the formulation is sufficient for us.
So, all we have to do is search for simple pan-digital numbers only among 7-digit and 4-digit numbers, so let’s change the first for loop:
for i in (7, 4):At this point, the entire program looks like this:
import math
import itertools
def is_prime(x: int):
if x % 2 == 0:
return x == 2
for i in range(3, math.ceil(x ** 0.5), 2):
if x % i == 0:
return False
return True
def main():
for i in (7, 4):
for j in itertools.permutations(list(map(str, list(range(i, 0, -1))))):
x = int(''.join(j))
if is_prime(x):
print(x)
return
if __name__ == '__main__':
main()Reducing the solution
Now let’s get down to shortening our program.
First, let’s get rid of the is_prime () function and the math library, which was used only in this function. The sympy module, which is unfortunately not standard, but which can be installed via pip install on the command line, is similar to our isprime () function. Let’s delete and replace the corresponding sections of the code:
import itertools
import sympy
def main():
for i in (7, 4):
for j in itertools.permutations(list(map(str, list(range(i, 0, -1))))):
x = int(''.join(j))
if sympy.isprime(x):
print(x)
return
if __name__ == '__main__':
main()Let’s remove the check for launching as the main application, remove unnecessary parentheses in for, remove the creation of a list from map, since map returns an iterable type that can be fed to the input of itertools.permutations:
import itertools
import sympy
def main():
for i in 7, 4:
for j in itertools.permutations(map(str, list(range(i, 0, -1)))):
x = int(''.join(j))
if sympy.isprime(x):
print(x)
return
main()Now I ask the lovers and passionate fans of pep-8 to turn their backs on the screen. Imports of several libraries on one line, the use of different module names and the removal of spaces after commas are coming.
import itertools as t,sympy
def m():
for i in 7,4:
for j in t.permutations(map(str,list(range(i,0,-1)))):
x = int(''.join(j))
if sympy.isprime(x):
print(x)
return
m()Note that accessing sympy under a different name is not profitable, since double writing “sympy” (when importing and when accessing) will take 10 characters, and renaming (for example, “sympy as s”) and calling (“s”) – already 11.
It’s already quite compact, isn’t it?
And now is the time for controversial decisions – you need to get rid of the function. But how, after all, we need to exit 2 loops at once, and the usual break cannot be used? After displaying the answer, simply exit the program. Despite the fact that you will hardly have time to see the answer with your eye, formally it will be displayed. If you do not exit, then the program will give 2 answers, and only the first is correct. It would be possible to do some forbidden operation, in the spirit of division by zero, but then an error message will be displayed in the console, that is, something other than a response.
You can use exit () or quit () to exit the program, but they are the same in length, so there is no difference. I will choose exit ()
So the program looks like this:
import itertools as t,sympy
for i in 7,4:
for j in t.permutations(map(str,list(range(i,0,-1)))):
x=int(''.join(j))
if sympy.isprime(x):
print(x)
exit()The final touch remains: remove the only extra transition to the next line and the tabulation character:
import itertools as t,sympy
for i in 7,4:
for j in t.permutations(map(str,list(range(i,0,-1)))):
x=int(''.join(j))
if sympy.isprime(x):
print(x);exit()Hurray, comrades! The program is only 159 characters long. If you have ideas on how you can reduce the code even less, write in the comments.
