Changing Pure Function in Module

[Fl...@safebunch.com]

Hi All,

thank you to all who continue to respond to all of my questions ... and there
are always plenty of them.

I have the following function embedded in the findD code below.

a[1] =5;

a[n_]:= a[n] = (-1)^(n+1) (Abs[a[n-1]]+2)

In[225]:=
findD[n_]:=
Module[{c=0},NestWhile[(c++;(-1)^c(Abs[#]+2))&,5,JacobiSymbol[#,n]!=-1&]]

I would like to change the pure function to use the following (cleaner) function
that requires no starting value (and starts for n = 1).

In[255]:=
a[n_]:= a[n]= (-1)^(n+1)*(2n + 3)

Also, it would be important to test n prior to calling findD. If n is a perfect
square, findD will "never" converge. Is there a simple way to test if n is
square and tell the user ... try again ... n is a perfect square.

Again thank you for all of the help ... Wilson

[Jens-Peer Kuska]

Hi,

> I have the following function embedded in the findD code below.
>
> a[1] =5;
>
> a[n_]:= a[n] = (-1)^(n+1) (Abs[a[n-1]]+2)
>
> In[225]:=
> findD[n_]:=
> Module[{c=0},NestWhile[(c++;(-1)^c(Abs[#]+2))&,5,JacobiSymbol[#,n]!=-1&]]
>
> I would like to change the pure function to use the following (cleaner) function
> that requires no starting value (and starts for n = 1).
>
> In[255]:=
> a[n_]:= a[n]= (-1)^(n+1)*(2n + 3)

So just do it, but with

a[n_Integer]/; Positive[n]:= a[n]= (-1)^(n+1)*(2n + 3)

the code is *not* "cleaner" it is just with out the recursion.

Why not use

a[n_Integer] /; Positive[n] := a[n] = (-1)^(n + 1)*(2n + 3)

and

findD1[n_] /; Head[Sqrt[n]] =!= Integer :=
Module[{i = 1, ai},
While[True,
If[JacobiSymbol[ ai = a[i++] , n] == -1, Break[]];
];
ai
]

>
> Also, it would be important to test n prior to calling findD. If n is a perfect
> square, findD will "never" converge. Is there a simple way to test if n is
> square

PerfectSquareQ[n_Integer]:=Head[Sqrt[n]] === Integer

Regards
Jens

[Ranko Bojanic]

Hi Wilson:
Now that we know exactly what you want, it is easy to write a module for FindD:

FindD[n_]:=Module[{c=1,a},If[IntegerQ[Sqrt[n]],a="n is a perfect square",
While[JacobiSymbol[(-1)^(c+1)(2c+3),n]é-1,c=c+1];
a=(-1)^(c+1)(2c+3)];
Return[a]]

FindD[1929321]
n is a perfect square

FindD[567134594567891251143216731]
-15

Regards,
Ranko

In Message 42/124 From Fl...@safebunch.com Jul 12,01 02:52:35 AM-0400
Wilson wrote:

> Hi All,
>
> thank you to all who continue to respond to all of my questions ... and there
> are always plenty of them.
>

> I have the following function embedded in the findD code below.
>
> a[1] =5;
>
> a[n_]:= a[n] = (-1)^(n+1) (Abs[a[n-1]]+2)
>
> In[225]:=
> findD[n_]:=
> Module[{c=0},NestWhile[(c++;(-1)^c(Abs[#]+2))&,5,JacobiSymbol[#,n]!=-1&]]
>
> I would like to change the pure function to use the following (cleaner) function
> that requires no starting value (and starts for n = 1).
>
> In[255]:=
> a[n_]:= a[n]= (-1)^(n+1)*(2n + 3)
>

> Also, it would be important to test n prior to calling findD. If n is a perfect
> square, findD will "never" converge. Is there a simple way to test if n is

[Orestis Vantzos]

squareQ[n_Integer] := IntegerQ[Sqrt[n]]
Orestis
<Fl...@safebunch.com> wrote in message news:9ijhui$ri5$1...@smc.vnet.net...

[Daniel Lichtblau]

Fl...@safebunch.com wrote:
>
> [...]

> Also, it would be important to test n prior to calling findD. If n is
> a perfect square, findD will "never" converge. Is there a simple way
> to test if n is square and tell the user ... try again ... n is a
> perfect square.
>
> Again thank you for all of the help ... Wilson

With regards to this, some care should be exercised when using the
proposed IntegerQ{Sqrt[n]] test. Specifically, if n is large, this can
be quite slow. A (usually) faster test involves taking a numerical
approximation to the square root and checking that it is equal to its
rounded value.

squaretest1[ee_] := IntegerQ[Sqrt[ee]]

squaretest2[ee_] := Module[{prec=Log[10.,ee], sqrt},
sqrt = Sqrt[N[ee, prec+$MachinePrecision]];
sqrt == Round[sqrt]
]

We'll try them on a random large number, its square, and the square plus
1.

aa[digits_] := Random[Integer, 10^digits-1]
int = aa[10^5];
int2 = int^2;

In[50]:= Timing[squaretest1[int]]
Out[50]= {10.14 Second, False}

In[51]:= Timing[squaretest2[int]]
Out[51]= {0.51 Second, False}

In[54]:= Timing[squaretest1[int2]]
Out[54]= {0.66 Second, True}

In[55]:= Timing[squaretest2[int2]]
Out[55]= {1.1 Second, True}

In[56]:= Timing[squaretest1[int2+1]]
Out[56]= {10.76 Second, False}

In[57]:= Timing[squaretest2[int2+1]]
Out[57]= {1.1 Second, False}

The "naive" method wins only when we actually have a perfect square.
This is because Power uses a numerical approximation itself in internal
code to find the square root, in case it is exact. But most numbers are
not squares, so the explicit numeric approximation method will be better
if inputs tend to be large and random (or at least not heavily skewed
toward perfect squares).

Daniel Lichtblau
Wolfram Research