Curzon numbers: Difference between revisions
Content added Content deleted
m (→{{header|Quackery}}: tidy up) |
(Added solution for Pascal.) |
||
Line 372: | Line 372: | ||
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 |
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 |
||
Thousandth Curzon with k = 10: 46845 |
Thousandth Curzon with k = 10: 46845 |
||
</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 |
|||
</pre> |
</pre> |
||