#include <stdio.h> #include <stdlib.h> #define TRY_MAX 5000 /* checking the base cases for Henzel's lemma */ long long gcd( long long i, long long j ) { long long temp; while( j ) { temp = j; j = i % j; i = temp; } return i; } int main( int argc, char **argv ) { char iswinner[TRY_MAX]; /* actual outputs of the program */ int success; char flag[TRY_MAX]; int count; long int start=2; long int inc=1; long long int i, k, n, r1, r2, r3, r4, d1, d2, d3, d4; for( i = 0; i < TRY_MAX; i++ ) flag[i] = 1; if( flag == NULL ) { fprintf( stderr, "Couldn't allocate flag[] array.\n" ); return 1; } /* if increment is given use it */ if( argc > 2 ) { fprintf( stderr, "arg2: %s\n" , argv[2] ); inc = strtol( argv[2], NULL, 10 ); if( inc != 1 ) { fprintf( stderr, "sorry -- only increments of 1...." ); inc = 1; } } /* if start is given, use it */ if( argc > 1 ) { fprintf( stderr, "arg1: %s\n" , argv[1] ); start = strtol( argv[1], NULL, 10 ); } fprintf( stderr, "start: %ld inc: %ld\n", start, inc ); for( n = start; n < TRY_MAX; n += inc ) { /* We'll count down when we mark off different hits */ count = n; /* fprintf( stderr, "%lld,\r", n ); */ /* Reset all of the hits */ for( i = 0; i < n; i++ ) flag[i]=1; for( k = 0; k < n; k++ ) { /* calculate the 4 polynomials */ r1 = ( 3*k*k ) % n; d1 = 6*k % n; r2 = ( 3*k+1 )*k % n; d2 = (6*k+1) % n; r3 = ( 3*k+2 )*k % n; d3 = (6*k+2) % n; r4 = (( 3*k+3 )*k + 1 ) % n; d4 = (6*k+3) % n; /* one sanity check, just to make sure */ if( r1 < 0 ) { fprintf( stderr, "r1 is negative\n" ); exit( 1 ); } /* check each result agains our list */ /* cross off if the number is hit by some k, with an invertible derivative at k */ if( flag[r1] && gcd(d1,n) == 1 ) { flag[r1] = 0; count--; } if( flag[r2] && gcd(d2,n) == 1 ) { flag[r2] = 0; count--; } if( flag[r3] && gcd(d3,n) == 1 ) { flag[r3] = 0; count--; } if( flag[r4] && gcd(d4,n) == 1 ) { flag[r4] = 0; count--; } } if( !count ) { fprintf( stdout, "%lld\n", n ); fflush( stdout ); iswinner[n] = 1; } else { iswinner[n] = 0; } } exit( 0 ); }