Curzon numbers: Difference between revisions

</pre>

=={{header|Pascal}}==

A console application in Free Pascal, created with the Lazarus IDE.

It isn't clear why the task description says "generalized Curzon numbers only exist for even base integers." If k >= 3 is an odd base, then, besides the trivial solution n = 1, it can be checked that n = k^(k-1) is a Curzon number according to the given definition. It seems from the output below that Curzon numbers with an odd base are much scarcer than those with an even base.

<lang pascal>

program CurzonNumbers;

uses SysUtils;

const

MAX_CURZON_MEG = 100;

RC_LINE_LENGTH = 66;

procedure ListCurzonNumbers( base : integer);

var

k, n, m, x, testBit, maxCurzon : uint64;

nrHits : integer;

lineOut : string;

begin

maxCurzon := 1000000*MAX_CURZON_MEG;

k := uint64( base);

nrHits := 0;

n := 0;

WriteLn;

if Odd( base) then WriteLn( SysUtils.Format(

'Curzon numbers with base %d up to %d million', [base, MAX_CURZON_MEG]))

else WriteLn( SysUtils.Format(

'First 50 Curzon numbers with base %d', [base]));

lineOut := '';

repeat

inc(n); // possible (generalized) Curzon number

m := k*n + 1; // modulus

testBit := 1;

repeat testBit := testBit shl 1 until testBit > n;

testBit := testBit shr 2;

// Calculate k^n modulo m

x := k;

while testBit > 0 do begin

x := (x*x) mod m;

if (testBit and n) <> 0 then x := (x*k) mod m;

testBit := testBit shr 1;

end;

// n is a Curzon number to base k iff k^n + 1 is divisible by m

if (x + 1) mod m = 0 then begin

inc( nrHits);

if Odd( base) then

lineOut := lineOut + ' ' + SysUtils.IntToStr( n)

else if (nrHits <= 50) then

lineOut := lineOut + SysUtils.Format( '%5d', [n]);

if Length( lineOut) >= RC_LINE_LENGTH then begin

WriteLn( lineOut); lineOut := '';

end

else if (nrHits = 1000) then begin

if lineOut <> '' then begin

WriteLn( lineOut); lineOut := '';

end;

WriteLn( SysUtils.Format( '1000th = %d', [n]));

end;

end;

until (n = maxCurzon) or (nrHits = 1000);

if lineOut <> '' then WriteLn( lineOut);

end;

begin

ListCurzonNumbers( 2);

ListCurzonNumbers( 4);

ListCurzonNumbers( 6);

ListCurzonNumbers( 8);

ListCurzonNumbers(10);

ListCurzonNumbers( 3);

ListCurzonNumbers( 5);

ListCurzonNumbers( 7);

ListCurzonNumbers( 9);

ListCurzonNumbers(11);

end.

</lang>

{{out}}

<pre>

First 50 Curzon numbers with base 2

1 2 5 6 9 14 18 21 26 29 30 33 41 50

53 54 65 69 74 78 81 86 89 90 98 105 113 114

125 134 138 141 146 153 158 165 173 174 186 189 194 198

209 210 221 230 233 245 249 254

1000th = 8646

First 50 Curzon numbers with base 4

1 3 7 9 13 15 25 27 37 39 43 45 49 57

67 69 73 79 87 93 97 99 105 115 127 135 139 153

163 165 169 175 177 183 189 193 199 205 207 213 219 235

249 253 255 265 267 273 277 279

1000th = 9375

First 50 Curzon numbers with base 6

1 6 30 58 70 73 90 101 105 121 125 146 153 166

170 181 182 185 210 233 241 242 266 282 290 322 373 381

385 390 397 441 445 446 450 453 530 557 562 585 593 601

602 605 606 621 646 653 670 685

1000th = 20717

First 50 Curzon numbers with base 8

1 14 35 44 72 74 77 129 131 137 144 149 150 185

200 219 236 266 284 285 299 309 336 357 381 386 390 392

402 414 420 441 455 459 470 479 500 519 527 536 557 582

600 602 617 639 654 674 696 735

1000th = 22176

First 50 Curzon numbers with base 10

1 9 10 25 106 145 190 193 238 253 306 318 349 385

402 462 486 526 610 649 658 678 733 762 810 990 994 1033

1077 1125 1126 1141 1149 1230 1405 1422 1441 1485 1509 1510 1513 1606

1614 1630 1665 1681 1690 1702 1785 1837

1000th = 46845

Curzon numbers with base 3 up to 100 million

1 9 3825 6561 102465 188505 190905 1001385 1556985 3427137 5153577

5270625 5347881 13658225 14178969 20867625 23828049 27511185 29400657

48533625 80817009 83406609 89556105

Curzon numbers with base 5 up to 100 million

1 625 57057 7748433 30850281

Curzon numbers with base 7 up to 100 million

1 135 5733 11229 42705 50445 117649 131365 168093 636405 699825 1269495

2528155 4226175 6176709 6502545 9365265 9551115 13227021 14464485

14912625 20859435 26903605 28251265 30589905 32660901 37597329 41506875

42766465 55452075 56192535

Curzon numbers with base 9 up to 100 million

1 81 558657 43046721 64734273

Curzon numbers with base 11 up to 100 million

1 2233 1623457 2213497 5413617 6306993 7567945 8054145 45750705 83024865

84034665