1
$\begingroup$

We know that any natural number $n$ can be decomposed as $p_1^{k_1}p_2^{k_2}...p_n^{k_n}$. I am looking for numbers which have $k_1=k_2=k_3=....=k_n=1$ i.e. given a number n, identify if it has all the $k_i=1$. I am looking for fast solutions, heuristics are welcome. One can assume that primes upto $n$ are stored.

Edit: $p_1, p_2, ....p_n$ are any primes and not necessarily the first n primes.

$\endgroup$
  • 2
    $\begingroup$ This is usually referred to as $p_n$-primorial. It is written $p_n!!$ or $p_n\#.$ The numbers of this type are 2,6,30,210,... etc. $\endgroup$ – daniel Dec 11 '14 at 12:49
  • 1
    $\begingroup$ But I don't know what you mean when you say you are looking for solutions. $\endgroup$ – daniel Dec 11 '14 at 13:01
  • $\begingroup$ I presume they mean given a number $n$ test whether it is of that form. $\endgroup$ – meta Dec 11 '14 at 13:47
  • 1
    $\begingroup$ hmmm....so I suppose I am looking for a test for squarefree numbers. $\endgroup$ – sudeepdino008 Dec 11 '14 at 15:58
  • 1
    $\begingroup$ No one has found a way to test numbers for squarefreeness that's any faster than factoring them. See, for example, mathoverflow.net/questions/16098/… $\endgroup$ – Gerry Myerson Dec 12 '14 at 9:14
1
$\begingroup$

You are looking for squarefree numbers. Unfortunately, as pointed out in the comments, no test faster than factoring has been developed to determine whether a number is squarefree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.