3
$\begingroup$

I'm sorry if this is an obvious question, but I'm a newbie and googling didn't help me much.

Is there a way in Mathematica to generate a number q coprime with p without resorting to do it "by hand" by iterating over a list of random numbers and using CoprimeQ?

I see how the likelihood of hitting a coprime soon is pretty good, but I wonder if there is a cleaner, or, if you want, more Mathematica-like way to do it.

Thank you very much.

Improve this question
$\endgroup$
  • 3
    $\begingroup$ just FYI the brute force approach (While[ ! CoprimeQ[n , i = RandomInteger[n]]]; i) is much faster than the "more elegant" answers.. $\endgroup$ – george2079 Apr 15 '15 at 15:08
  • $\begingroup$ @george2079 hey, I like more elegant answer! $\endgroup$ – rcollyer Apr 15 '15 at 18:59
5
$\begingroup$

This is a straightforward function generating a random coprime number less than given natural number x.

cpr[x_Integer]/; x > 1 := 
  RandomChoice @ Pick[ Range[x], CoprimeQ[ x, Range[x]]]

e.g.

cpr[341]

79

However if we are to deal with larger numbers the given definition is not very convenient therfore it is reasonable to provide another definition yielding a random coprime between k and m e.g.

cpr[x_Integer, k_Integer, m_Integer] /; x > m > k > 1 := 
  RandomChoice @ Pick[ Range[k, m], CoprimeQ[ x, Range[k, m]]]

for a choice between k and m

e.g.

cpr[32059725, 21172781, 25565647]

21921206

If one chooses an appropriate range there are always some coprimes unless k and m are too close.

Improve this answer
$\endgroup$
  • 3
    $\begingroup$ I believe this is a solution that the OP has specifically excluded in their question. Better if we can do it without having to generate a list of candidates and only after that verify whether they are coprime or not. $\endgroup$ – Oleksandr R. Apr 15 '15 at 11:30
  • $\begingroup$ @OleksandrR. The provided solution is quite good and very Mathematica-like one. The OP as a newbie excludes iterating over a list of random numbers and then using CoprimeQ. There is no iteration, no random list, just a range of numbers and simply CoprimeQ for which there is no better substitution. Just a reliable solution, if you can see a better one, clarify what you mean. I guess you might have suggested another mathematical approach if it had existed but I susspect it hadn't. Unless you find the solution by rcollyer better, however frankly I don't. $\endgroup$ – Artes Apr 16 '15 at 13:25
3
$\begingroup$

Using the definition of coprime, it is straightforward to construct a function that will do as you ask.

Clear[randomCoprime];
randomCoprime[n_Integer, k_Integer : Automatic] :=
Block[{count, maxP, factors, allowedF},
  maxP = PrimePi@Sqrt@n;
  factors = PrimePi@FactorInteger[n][[All,1]];
  count = If[k===Automatic, RandomInteger[{2, maxP}], k];
  allowedF = Complement[Range[2,maxP], factors];
  Times@@Prime[RandomChoice[allowedF, count]]
]

It works by indexing the prime factors of n via PrimePi, generating a list of allowed prime indices, and then randomly choosing from that list. The final number is reconstructed using Prime. In the function, k determines the number of coprime factors chosen, and it will be randomly determined, if not specified.

Improve this answer
$\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.