Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #11739 > unrolled thread

primitive root error

Started byDan Dubin <ddubin@ucsd.edu>
First post2012-09-14 04:15 +0000
Last post2012-09-18 07:46 +0000
Articles 4 — 4 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  primitive root error Dan Dubin <ddubin@ucsd.edu> - 2012-09-14 04:15 +0000
    Re: primitive root error daniel.lichtblau0@gmail.com - 2012-09-15 07:45 +0000
    Re: primitive root error Andrzej Kozlowski <akozlowski@gmail.com> - 2012-09-16 07:22 +0000
    Re: primitive root error danl@wolfram.com - 2012-09-18 07:46 +0000

#11739 — primitive root error

FromDan Dubin <ddubin@ucsd.edu>
Date2012-09-14 04:15 +0000
Subjectprimitive root error
Message-ID<k2ub15$h9h$1@smc.vnet.net>
The number theoretic function PrimitiveRoot[n]  is supposed to give the 
smallest generator for the multiplicative group of integers module n 
relatively prime to n.  However, Mathematica 8  says that
PrimitiveRoot[18] equals 11. This is incorrect. While this is a 
generator, it is not the smallest generator of the group. The correct 
answer is 5:

In[1]:= Table[Mod[5^n, 18], {n, 0, 6}]

Out[1]= {1, 5, 7, 17, 13, 11, 1}

[toc] | [next] | [standalone]


#11754

Fromdaniel.lichtblau0@gmail.com
Date2012-09-15 07:45 +0000
Message-ID<k31bn7$mqc$1@smc.vnet.net>
In reply to#11739
On Thursday, September 13, 2012 11:16:47 PM UTC-5, Dan Dubin wrote:
> The number theoretic function PrimitiveRoot[n]  is supposed to give the 
> 
> smallest generator for the multiplicative group of integers module n 
> 
> relatively prime to n.  However, Mathematica 8  says that
> 
> PrimitiveRoot[18] equals 11. This is incorrect. While this is a 
> 
> generator, it is not the smallest generator of the group. The correct 
> 
> answer is 5:
> 
> 
> 
> In[1]:= Table[Mod[5^n, 18], {n, 0, 6}]
> 
> 
> 
> Out[1]= {1, 5, 7, 17, 13, 11, 1}

Me, I'd call that a mistake in the documentation. Anyway, you can get the smallest by resorting to a crude, nay, barbaric tactic: invoke Wolfram|Alpha to find all the primitive roots.

In[71]:= WolframAlpha["primitive roots of 18", "MathematicaResult"]

Out[71]= {5, 11}

Daniel Lichtblau
Wolfram Research


[toc] | [prev] | [next] | [standalone]


#11759

FromAndrzej Kozlowski <akozlowski@gmail.com>
Date2012-09-16 07:22 +0000
Message-ID<k33un1$qtc$1@smc.vnet.net>
In reply to#11739
On 15 Sep 2012, at 09:38, daniel.lichtblau0@gmail.com wrote:

> On Thursday, September 13, 2012 11:16:47 PM UTC-5, Dan Dubin wrote:
>> The number theoretic function PrimitiveRoot[n]  is supposed to give the
>>
>> smallest generator for the multiplicative group of integers module n
>>
>> relatively prime to n.  However, Mathematica 8  says that
>>
>> PrimitiveRoot[18] equals 11. This is incorrect. While this is a
>>
>> generator, it is not the smallest generator of the group. The correct
>>
>> answer is 5:
>>
>>
>>
>> In[1]:= Table[Mod[5^n, 18], {n, 0, 6}]
>>
>>
>>
>> Out[1]= {1, 5, 7, 17, 13, 11, 1}
>
> Me, I'd call that a mistake in the documentation. Anyway, you can get the smallest by resorting to a crude, nay, barbaric tactic: invoke Wolfram|Alpha to find all the primitive roots.
>
> In[71]:= WolframAlpha["primitive roots of 18", "MathematicaResult"]
>
> Out[71]= {5, 11}
>
> Daniel Lichtblau
> Wolfram Research
>
>
>


This does indeed seem a little barbaric since:


WolframAlpha["primitive roots of 18", "MathematicaResult"] // Timing

{1.87481,{5,11}}


Select[Range[18],
  MultiplicativeOrder[#, 18] == EulerPhi[18] &] // Timing

{0.000347,{5,11}}


Andrzej Kozlowski

[toc] | [prev] | [next] | [standalone]


#11786

Fromdanl@wolfram.com
Date2012-09-18 07:46 +0000
Message-ID<k398sa$9oh$1@smc.vnet.net>
In reply to#11739
On Sunday, September 16, 2012 2:23:26 AM UTC-5, Andrzej Kozlowski wrote:
> On 15 Sep 2012, at 09:38, somebody wrote:
> [...]
> >
> > Me, I'd call that a mistake in the documentation. Anyway, you can get the smallest by resorting to a crude, nay, barbaric tactic: invoke Wolfram|Alpha to find all the primitive roots.
>
> > In[71]:= WolframAlpha["primitive roots of 18", "MathematicaResult"]
> >
> > Out[71]= {5, 11}
> [...]
> >
>
> This does indeed seem a little barbaric since:
>
>
> WolframAlpha["primitive roots of 18", "MathematicaResult"] // Timing
> 
> {1.87481,{5,11}}
> 
> Select[Range[18],
>
>   MultiplicativeOrder[#, 18] == EulerPhi[18] &] // Timing
>
> {0.000347,{5,11}}
>
>
> Andrzej Kozlowski

Might in part be an issue with establishing a connection to Alpha. It was around 4x faster for me. Repeating brings it to around .03 seconds. Given that this involves a round trip to Alpha, the factor of 10 dominance of that vs. the actual computation is not too surprising.

This variant might be noticeably faster than what you tried though. (Note to the uninitiated: Don't try the other method on this).

WolframAlpha["primitive roots of Prime[18]^18",
  "MathematicaResult"] // Timing

It will give the smallest and largest roots, alomg with the total count.

Daniel Lichtblau
Wolfram Research

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web