Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #11739 > unrolled thread
| Started by | Dan Dubin <ddubin@ucsd.edu> |
|---|---|
| First post | 2012-09-14 04:15 +0000 |
| Last post | 2012-09-18 07:46 +0000 |
| Articles | 4 — 4 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
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
| From | Dan Dubin <ddubin@ucsd.edu> |
|---|---|
| Date | 2012-09-14 04:15 +0000 |
| Subject | primitive 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]
| From | daniel.lichtblau0@gmail.com |
|---|---|
| Date | 2012-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]
| From | Andrzej Kozlowski <akozlowski@gmail.com> |
|---|---|
| Date | 2012-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]
| From | danl@wolfram.com |
|---|---|
| Date | 2012-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