Pseudosquare

Author

Eric W. Weisstein
September 24, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheory/Pseudosquare.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Pseudosquare.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Definition

Pseudosquare[p_]:=Module[{q=Table[Prime[n],{n,2,PrimePi[p]}],lp=3},
While[IntegerQ[Sqrt[lp]]||Mod[lp,8]!=1||!Union[JacobiSymbol[lp,#]&/@q]=={1},lp++
];
lp
]

Pseudosquare2[p_]:=Module[{q=Table[Prime[n],{n,2,PrimePi[p]}],lp=3},
While[IntegerQ[Sqrt[lp]]||Mod[lp,8]!=1||(JacobiSymbol[lp,#]≠1&)/@(Or@@q),lp++
];
lp
]

Enumeration

Table[Pseudosquare[Prime[n]],{n,2,8}]//Timing

Table[Pseudosquare[Prime[n]],{n,2,15}]//Timing

Table[Prime[n],{n,2,15}]