Number Theory


How to Check if a Number is Prime Using a Finite Definite Integral

Authors: Jesús Sánchez

b=0; p=input('Input a number : '); m=fix((p+1)/2); for k=2:m+1; fun=@(w) exp(p.*1j.*w).*exp(-2.*k.*1j.*w).*(1-exp(-m.*k.*1j.*w))./(1-exp(-k.*1j.*w)); a=integral(fun,-pi,pi); b=b+a; end; b=b/(2*pi); disp(b); Above simple MATLAB/Octave program, can detect if a number is prime or not. If the result is zero (considering zero being less than 1e-5), the number introduced is a prime. If the result is an integer, this result will tell us how many permutations of two divisors, the input number has. As you can check, no recurrent division by odd or prime numbers is done. Just this strange integral: 1/2π ∫_(-π)^π▒〖e^pjω (∑_(k=2)^(k=m+1)▒〖e^(-2kjω) ((1-e^(-mkjω))/(1-e^(-kjω) )) 〗)dω 〗 Being p the number that we want to check if it is a prime or not. And being m whatever integer number higher than (p+1)/2(the lowest, the most efficient the operation). As k and ω are independent variables, the sum can be taken outside the integral (as it is in the above program). To get to this point, we will do the following. First, we will create a domain with all the composite numbers. This is easy, as you can just multiply one by one all the integers (greater or equal than 2) in that domain. So, you will get all the composite numbers (not getting any prime) in that domain. Then, we will use the Fourier transform to change from this original domain (called discrete time domain in this regards) to the frequency domain. There, we can “ask”, using Parseval’s theorem, if a certain number is there or not. The use of Parseval’s theorem leads to the above integral. If the number p that we want to check is not in the domain, the result of the integral is zero and the number is a prime. If instead, the result is an integer, this integer will tell us how many permutations of two divisors the number p has. And, in consequence information how many factors, the number p has. So, for any number p lower than 2m-1, you can check if it is prime or not, just making the numerical definite integration (but even this integral, if no further developments are done, the numerical integration is inefficient computing-wise compared with brute-force checking for example). To be added, is the question regarding the level of accuracy needed (number of decimals and number of steps in the numerical integration) to have a reliable result for large numbers. This will be commented on the paper, but a separate study will be needed to have detailed conclusions. Of course, the best would be that in the future, an analytical result (or at least an approximation) for the summation or for the integration is achieved.

Comments: 21 Pages.

Download: PDF

Submission history

[v1] 2018-12-24 05:12:29
[v2] 2018-12-25 07:45:30

Unique-IP document downloads: 43 times is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus