SOLSTRAS - Solovay-Strassen Inverted

no tags 

Let us denote the set of all prime numbers by the symbol P. The Solovay-Strassen algorithm determines whether a given positive odd integer n>2 belongs to P.

The Legendre function sig for number nin N with parameter sin N (s<n) is defined by the formula sig(n,s)=s(n-1)/2 mod n. The symbol mod is defined in such a way as to return the result with the smallest possible absolute value, from the range (-n/2, n/2].

The Jacobi function jac for number nin N with parameter sin N (s<n) is given as:
jac(n,s)=
cases
sig(n,s),   if  ninP
k
product
i=1
sig(pi,s),
  if   n=
k
product
i=1
 pi, where all  pi inP

It is interesting to note that for given n and s, the values of sig(n,s) and jac(n,s) can be computed in O((log2 n)2) time. For particulars consult an encyclopedia, such as MathWorld.

The deterministic version of the Solovay-Strassen primality-test algorithm is given below.

algorithm Solovay-Strassen (n)
var s;
begin
    for s in {1,2,3,4,...,n} do
        if sig(n,s)neqjac(n,s)
            then return "n is composite (detected at attempt <s>)";
    return "n is prime";
end.

Task

We are not asking you to implement the Solovay-Strassen algorithm, this would be far too easy :). Instead, try to find values of n, for which the output of the algorithm would be "n is composite (detected at attempt 1)", "n is composite (detected at attempt 2)", and so on. Write out as many of these values as you can in consecutive lines, and try to keep them as small as possible.

Scoring

The score awarded to your program is the total of all points given for its individual lines.

The i-th line output by your program should contain exactly one positive odd integer n>2 of no more than 500 decimal digits. If Solovay-Strassen(n) yields the answer "n is composite (detected at attempt i)", you will receive i/log10 n points for this line, if not - your program will be considered incorrect. Output 0 if you don't want a line to be assessed. Only the first 1000 lines of output are taken into account.

Example

A program outputing:

0
0
561

will receive 3/log10 561 = 1.091 points.


hide comments
dbag007: 2016-11-24 06:34:51

been breaking my head over this :( any hints ?

Robert Gerbicz: 2014-02-25 01:27:40

Amazing, now I have a solution (within constraints and without internal errors) for every (possible) line. Almost 10 years after this problem posted.

Wolfram: 2009-12-13 22:07:10

Jargon, the problem statement defines the Legendre function sig(n, s) only for s less than n. 4 is not less than 3, thus sig(3, 4) is not defined.

Jargon: 2009-12-12 19:30:09

Edit: I was mistaken and I retract my statement.

Last edit: 2010-05-14 01:03:56
Wolfram: 2009-12-11 22:19:14

The problem description is not correct.
For example, jac(9, 4) is defined as sig(3, 4) * sig(3, 4), but sig(3, 4) is not defined.


Added by:Konrad Piwakowski
Date:2004-07-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Thanks to Daniel Grzonkowski for valuable comments