Curzon numbers: Difference between revisions
(35 intermediate revisions by 25 users not shown) | |||
Line 30: | Line 30: | ||
<br> |
<br> |
||
=={{header|11l}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="11l"> |
|||
F is_curzon(n, k) |
|||
V m = k * n + 1 |
|||
R pow(Int64(k), n, m) + 1 == m |
|||
L(k) [2, 4, 6, 8, 10] |
|||
V n = 1 |
|||
[Int] curzons |
|||
L curzons.len < 1000 |
|||
I is_curzon(n, k) |
|||
curzons.append(n) |
|||
n++ |
|||
print(‘Curzon numbers with k = ’k‘:’) |
|||
L(c) curzons[0.<50] |
|||
V i = L.index |
|||
print(f:‘{commatize(c):6}’, end' I (i + 1) % 25 == 0 {"\n"} E ‘’) |
|||
print(‘ Thousandth Curzon with k = ’k‘: ’curzons[999]".\n") |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 2: 8646. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 4: 9375. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 6: 20717. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 8: 22176. |
|||
Curzon numbers with k = 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 1,033 1,077 1,125 1,126 1,141 1,149 1,230 1,405 1,422 1,441 1,485 1,509 1,510 1,513 1,606 1,614 1,630 1,665 1,681 1,690 1,702 1,785 1,837 |
|||
Thousandth Curzon with k = 10: 46845. |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
{{Trans|C++}} |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # find some generalised Curzon numbers - translation of the C++ sample # |
|||
PROC modpow = ( LONG INT rqd base, rqd exp, mod )LONG INT: |
|||
IF mod = 1 |
|||
THEN 0 |
|||
ELSE |
|||
LONG INT result := 1; |
|||
LONG INT base := rqd base MOD mod; |
|||
LONG INT exp := rqd exp; |
|||
WHILE exp > 0 DO |
|||
IF ODD exp THEN |
|||
result TIMESAB base MODAB mod |
|||
FI; |
|||
base TIMESAB base MODAB mod; |
|||
exp OVERAB 2 |
|||
OD; |
|||
result |
|||
FI # modpow # ; |
|||
PROC is curzon = ( LONG INT n, k )BOOL: |
|||
BEGIN |
|||
LONG INT m = k * n + 1; |
|||
modpow( k, n, m ) + 1 = m |
|||
END # is curon # ; |
|||
FOR k FROM 2 BY 2 TO 10 DO |
|||
print( ( "Curzon numbers with base ", whole( k, 0 ), ":", newline ) ); |
|||
INT count := 0, n := 0; |
|||
WHILE n +:= 1; |
|||
count < 50 |
|||
DO |
|||
IF is curzon( n, k ) THEN |
|||
print( ( whole( n, -4 ) |
|||
, IF ( count +:= 1 ) MOD 10 = 0 THEN newline ELSE " " FI |
|||
) |
|||
) |
|||
FI |
|||
OD; |
|||
WHILE IF is curzon( n, k ) THEN count +:= 1 FI; |
|||
count < 1000 |
|||
DO |
|||
n +:= 1 |
|||
OD; |
|||
print( ( "1000th Curzon number with base ", whole( k, 0 ), ": ", whole( n, 0 ) ) ); |
|||
print( ( newline, newline ) ) |
|||
OD |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 Curzon number with base 2: 8646 |
|||
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 Curzon number with base 4: 9375 |
|||
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 Curzon number with base 6: 20717 |
|||
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 Curzon number with base 8: 22176 |
|||
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 Curzon number with base 10: 46845 |
|||
</pre> |
|||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">curzon?: function [n,base]-> |
||
zero? (inc base^n) % inc base*n |
zero? (inc base^n) % inc base*n |
||
Line 63: | Line 207: | ||
print ["\n1000th Curzon with base" withBase "=" oneThousandth withBase] |
print ["\n1000th Curzon with base" withBase "=" oneThousandth withBase] |
||
print "" |
print "" |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 111: | Line 255: | ||
1000th Curzon with base 10 = 46845</pre> |
1000th Curzon with base 10 = 46845</pre> |
||
=={{header|C}}== |
|||
{{trans|C++}} |
|||
<syntaxhighlight lang="c">#include <stdio.h> |
|||
#include <stdbool.h> |
|||
#include <stdint.h> |
|||
#include <locale.h> |
|||
uint64_t modPow(uint64_t base, uint64_t exp, uint64_t mod) { |
|||
if (mod == 1) return 0; |
|||
uint64_t result = 1; |
|||
base %= mod; |
|||
for (; exp > 0; exp >>= 1) { |
|||
if ((exp & 1) == 1) result = (result * base) % mod; |
|||
base = (base * base) % mod; |
|||
} |
|||
return result; |
|||
} |
|||
bool isCurzon(uint64_t n, uint64_t k) { |
|||
const uint64_t r = k * n; |
|||
return modPow(k, n, r+1) == r; |
|||
} |
|||
int main() { |
|||
uint64_t k, n, count; |
|||
setlocale(LC_NUMERIC, ""); |
|||
for (k = 2; k <= 10; k += 2) { |
|||
printf("Curzon numbers with base %ld:\n", k); |
|||
for (n = 1, count = 0; count < 50; ++n) { |
|||
if (isCurzon(n, k)) { |
|||
printf("%4ld ", n); |
|||
if (++count % 10 == 0) printf("\n"); |
|||
} |
|||
} |
|||
for (;;) { |
|||
if (isCurzon(n, k)) ++count; |
|||
if (count == 1000) break; |
|||
++n; |
|||
} |
|||
printf("1,000th Curzon number with base %ld: %'ld\n\n", k, n); |
|||
} |
|||
return 0; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
1,000th Curzon number with base 2: 8,646 |
|||
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 |
|||
1,000th Curzon number with base 4: 9,375 |
|||
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 |
|||
1,000th Curzon number with base 6: 20,717 |
|||
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 |
|||
1,000th Curzon number with base 8: 22,176 |
|||
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 |
|||
1,000th Curzon number with base 10: 46,845 |
|||
</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
<syntaxhighlight lang="cpp">#include <cstdint> |
|||
{{libheader|GMP}} |
|||
#include <iomanip> |
|||
#include <iostream> |
#include <iostream> |
||
#include <vector> |
#include <vector> |
||
uint64_t modpow(uint64_t base, uint64_t exp, uint64_t mod) { |
|||
#include <gmpxx.h> |
|||
if (mod == 1) |
|||
return 0; |
|||
uint64_t result = 1; |
|||
base %= mod; |
|||
for (; exp > 0; exp >>= 1) { |
|||
if ((exp & 1) == 1) |
|||
result = (result * base) % mod; |
|||
base = (base * base) % mod; |
|||
} |
|||
return result; |
|||
} |
|||
bool is_curzon( |
bool is_curzon(uint64_t n, uint64_t k) { |
||
const uint64_t r = k * n; |
|||
mpz_class p; |
|||
return modpow(k, n, r + 1) == r; |
|||
mpz_ui_pow_ui(p.get_mpz_t(), k, n); |
|||
return (p + 1) % (k * n + 1) == 0; |
|||
} |
} |
||
int main() { |
int main() { |
||
for ( |
for (uint64_t k = 2; k <= 10; k += 2) { |
||
std::cout << "Curzon numbers with base " << k << ":\n"; |
std::cout << "Curzon numbers with base " << k << ":\n"; |
||
uint64_t count = 0, n = 1; |
|||
for (; count < 50; ++n) { |
for (; count < 50; ++n) { |
||
if (is_curzon(n, k)) { |
if (is_curzon(n, k)) { |
||
Line 147: | Line 388: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 192: | Line 433: | ||
</pre> |
</pre> |
||
=={{header|EasyLang}}== |
|||
{{trans|FreeBASIC}} |
|||
<syntaxhighlight> |
|||
func pow_mod b power modulus . |
|||
x = 1 |
|||
while power > 0 |
|||
if power mod 2 = 1 |
|||
x = x * b mod modulus |
|||
. |
|||
b = b * b mod modulus |
|||
power = power div 2 |
|||
. |
|||
return x |
|||
. |
|||
for k = 2 step 2 to 10 |
|||
numfmt 0 0 |
|||
print "First 50 Curzon numbers using a base of " & k & ":" |
|||
numfmt 0 4 |
|||
n = 1 |
|||
count = 0 |
|||
repeat |
|||
m = k * n + 1 |
|||
p = pow_mod k n m + 1 |
|||
if p = m |
|||
count += 1 |
|||
if count <= 50 |
|||
write " " & n |
|||
if count mod 9 = 0 |
|||
print "" |
|||
. |
|||
. |
|||
. |
|||
until count = 1000 |
|||
n += 1 |
|||
. |
|||
print "" ; print "One thousandth: " & n |
|||
print "" |
|||
. |
|||
</syntaxhighlight> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2022-04-03}} |
{{works with|Factor|0.99 2022-04-03}} |
||
< |
<syntaxhighlight lang="factor">USING: grouping interpolate io kernel make math math.functions |
||
prettyprint ranges sequences ; |
prettyprint ranges sequences ; |
||
Line 209: | Line 490: | ||
curzon 10 group simple-table. ; |
curzon 10 group simple-table. ; |
||
2 10 2 <range> [ curzon. nl ] each</ |
2 10 2 <range> [ curzon. nl ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 247: | Line 528: | ||
1513 1606 1614 1630 1665 1681 1690 1702 1785 1837 |
1513 1606 1614 1630 1665 1681 1690 1702 1785 1837 |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
===Normal basic=== |
|||
<syntaxhighlight lang="freebasic">' limit: k * n +1 must be smaller then 2^32-1 |
|||
Function pow_mod(b As ULongInt, power As ULongInt, modulus As ULongInt) As ULongInt |
|||
' returns b ^ power mod modulus |
|||
Dim As ULongInt x = 1 |
|||
While power > 0 |
|||
If (power And 1) = 1 Then |
|||
x = (x * b) Mod modulus |
|||
End If |
|||
b = (b * b) Mod modulus |
|||
power = power Shr 1 |
|||
Wend |
|||
Return x |
|||
End Function |
|||
For k As ULongInt= 2 To 10 Step 2 |
|||
Print "The first 50 Curzon numbers using a base of "; k; ":" |
|||
Dim As ULongInt count, n = 1, p, m |
|||
Do |
|||
m = k * n +1 |
|||
p = pow_mod(k, n ,m) +1 |
|||
If p = m Then |
|||
count += 1 |
|||
If count <= 50 Then |
|||
Print Using "#####"; n; |
|||
If (count Mod 10) = 0 Then Print |
|||
ElseIf count = 1000 Then |
|||
Print : Print "One thousandth: "; n |
|||
Print : Print |
|||
Exit Do |
|||
End If |
|||
End If |
|||
n += 1 |
|||
Loop |
|||
Next |
|||
Sleep</syntaxhighlight>{{out}}<pre>The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 8646 |
|||
The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 9375 |
|||
The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 20717 |
|||
The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 22176 |
|||
The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 46845</pre> |
|||
===GMP version=== |
|||
{{libheader|GMP}} |
|||
<syntaxhighlight lang="freebasic">#include once "gmp.bi" |
|||
Dim As Longint t = Len(__mpz_struct) |
|||
Dim As mpz_ptr pow = Allocate(t) |
|||
Dim As mpz_ptr z = Allocate(t) |
|||
mpz_init(pow): mpz_init(z) |
|||
For k As Uinteger = 2 To 10 Step 2 |
|||
Print "The first 50 Curzon numbers using a base of"; k; ":" |
|||
Dim As Integer count = 0, n = 1 |
|||
mpz_set_si(pow,k) |
|||
Do |
|||
mpz_add_ui(z,pow,1) |
|||
Dim As Integer d = k*n + 1 |
|||
If mpz_divisible_ui_p(z,d) Then |
|||
count += 1 |
|||
If count <= 50 Then |
|||
Print Using "#####"; n |
|||
If (count Mod 25) = 0 Then Print |
|||
Elseif count=1000 Then |
|||
Print "One thousandth: "; n |
|||
Print : Print |
|||
Exit Do |
|||
End If |
|||
End If |
|||
n += 1 |
|||
mpz_mul_si(pow,pow,k) |
|||
Loop |
|||
Next k |
|||
Sleep</syntaxhighlight> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
Based on Version 1. |
|||
<lang go>package main |
|||
<syntaxhighlight lang="go">package main |
|||
import ( |
import ( |
||
Line 296: | Line 703: | ||
fmt.Println() |
fmt.Println() |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 344: | Line 751: | ||
One thousandth: 46845 |
One thousandth: 46845 |
||
</pre> |
|||
=={{header|Haskell}}== |
|||
<syntaxhighlight lang=Haskell> |
|||
import Data.List.Split ( chunksOf ) |
|||
isGeneralizedCurzon :: Integer -> Integer -> Bool |
|||
isGeneralizedCurzon base n = mod ( base ^ n + 1 ) ( base * n + 1 ) == 0 |
|||
solution :: Integer -> [Integer] |
|||
solution base = take 50 $ filter (\i -> isGeneralizedCurzon base i ) [1..] |
|||
printChunk :: [Integer] -> String |
|||
printChunk chunk = foldl1 (++) $ map (\i -> (take ( 4 - (length $ show i) ) |
|||
$ repeat ' ' ) ++ show i ++ " ") chunk |
|||
prettyPrint :: [Integer] -> [String] |
|||
prettyPrint list = map printChunk $ chunksOf 10 list |
|||
oneThousandth :: Integer -> Integer |
|||
oneThousandth base = last $ take 950 $ filter (\i -> isGeneralizedCurzon base i ) |
|||
[(last $ solution base) + 1 ..] |
|||
printBlock :: Integer -> [String] |
|||
printBlock base = ["first 50 Curzon numbers using a base of " ++ show base ++ " :"] |
|||
++ (prettyPrint $ solution base) ++ ["one thousandth at base " ++ show base ++ |
|||
": " ++ (show $ oneThousandth base)] ++ [take 50 $ repeat '-'] |
|||
main :: IO ( ) |
|||
main = do |
|||
blocks <- return $ concat $ map (\i -> printBlock i ) [2 , 4 , 6 , 8 , 10] |
|||
mapM_ putStrLn blocks</syntaxhighlight> |
|||
{{out}} |
|||
<pre>first 50 Curzon numbers using a base of 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 |
|||
one thousandth at base 2: 8646 |
|||
-------------------------------------------------- |
|||
first 50 Curzon numbers using a base of 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 |
|||
one thousandth at base 4: 9375 |
|||
-------------------------------------------------- |
|||
first 50 Curzon numbers using a base of 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 |
|||
one thousandth at base 6: 20717 |
|||
-------------------------------------------------- |
|||
first 50 Curzon numbers using a base of 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 |
|||
one thousandth at base 8: 22176 |
|||
-------------------------------------------------- |
|||
first 50 Curzon numbers using a base of 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 |
|||
one thousandth at base 10: 46845 |
|||
-------------------------------------------------- |
|||
</pre> |
|||
=={{header|J}}== |
|||
A simple test for whether a number is a (generalized) Curzon number is: |
|||
<syntaxhighlight lang="j">isCurzon =: 2&$: : (0 = * |&:>: ^)</syntaxhighlight> |
|||
Here, the monadic case uses 2 as the left argument for the dyadic case, which handles generalized Curzon numbers. |
|||
However, this is inefficient for large numbers, due to it explicitly exponentiating. |
|||
Since we test the remainder immediately after, we can use a special combination instead, |
|||
<syntaxhighlight lang="j">modpow =: {{ m&|@^ }} |
|||
isCurzon =: {{ |
|||
z =: >: x * y |
|||
z = >: x z modpow y |
|||
}}</syntaxhighlight> |
|||
This avoids performing the large exponentiation, which is significantly faster. |
|||
For generating the results: |
|||
<syntaxhighlight lang="j">generateCurzons =: {{ |
|||
found =. i. 0x |
|||
current =. 0x |
|||
while. 1000 > # found do. |
|||
if. y isCurzon current do. found =. found , current end. |
|||
current =. >: current |
|||
end. |
|||
y ; (5 10 $ found) ; {: found |
|||
}} |
|||
('Base';'First 50';'1000th') , generateCurzons"0 +:>:i.5</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
+----+-------------------------------------------------+------+ |
|||
|Base|First 50 |1000th| |
|||
+----+-------------------------------------------------+------+ |
|||
|2 | 1 2 5 6 9 14 18 21 26 29 |8646 | |
|||
| | 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 | | |
|||
+----+-------------------------------------------------+------+ |
|||
|4 | 1 3 7 9 13 15 25 27 37 39 |9375 | |
|||
| | 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 | | |
|||
+----+-------------------------------------------------+------+ |
|||
|6 | 1 6 30 58 70 73 90 101 105 121 |20717 | |
|||
| |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 | | |
|||
+----+-------------------------------------------------+------+ |
|||
|8 | 1 14 35 44 72 74 77 129 131 137 |22176 | |
|||
| |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 | | |
|||
+----+-------------------------------------------------+------+ |
|||
|10 | 1 9 10 25 106 145 190 193 238 253|46845 | |
|||
| | 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| | |
|||
+----+-------------------------------------------------+------+ |
|||
</pre> |
|||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java"> |
|||
public final class CurzonNumbers { |
|||
public static void main(String[] aArgs) { |
|||
for ( int k = 2; k <= 10; k += 2 ) { |
|||
System.out.println("Generalised Curzon numbers with base " + k + ":"); |
|||
int n = 1; |
|||
int count = 0; |
|||
while ( count < 50 ) { |
|||
if ( isGeneralisedCurzonNumber(k, n) ) { |
|||
System.out.print(String.format("%4d%s", n, ( ++count % 10 == 0 ? "\n" : " " ))); |
|||
} |
|||
n += 1; |
|||
} |
|||
while ( count < 1_000 ) { |
|||
if ( isGeneralisedCurzonNumber(k, n) ) { |
|||
count += 1; |
|||
} |
|||
n += 1; |
|||
} |
|||
System.out.println("1,000th Generalised Curzon number with base " + k + ": " + ( n - 1 )); |
|||
System.out.println(); |
|||
} |
|||
} |
|||
private static boolean isGeneralisedCurzonNumber(int aK, int aN) { |
|||
final long r = aK * aN; |
|||
return modulusPower(aK, aN, r + 1) == r; |
|||
} |
|||
private static long modulusPower(long aBase, long aExponent, long aModulus) { |
|||
if ( aModulus == 1 ) { |
|||
return 0; |
|||
} |
|||
aBase %= aModulus; |
|||
long result = 1; |
|||
while ( aExponent > 0 ) { |
|||
if ( ( aExponent & 1 ) == 1 ) { |
|||
result = ( result * aBase ) % aModulus; |
|||
} |
|||
aBase = ( aBase * aBase ) % aModulus; |
|||
aExponent >>= 1; |
|||
} |
|||
return result; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
Generalised 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 |
|||
1,000th Generalised Curzon number with base 2: 8646 |
|||
Generalised 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 |
|||
1,000th Generalised Curzon number with base 4: 9375 |
|||
Generalised 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 |
|||
1,000th Generalised Curzon number with base 6: 20717 |
|||
Generalised 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 |
|||
1,000th Generalised Curzon number with base 8: 22176 |
|||
Generalised 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 |
|||
1,000th Generalised Curzon number with base 10: 46845 |
|||
</pre> |
</pre> |
||
Line 354: | Line 996: | ||
'''Preliminaries''' |
'''Preliminaries''' |
||
< |
<syntaxhighlight lang="jq"># To take advantage of gojq's arbitrary-precision integer arithmetic: |
||
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in); |
||
Line 364: | Line 1,006: | ||
n; |
n; |
||
def printRows($m): _nwise($m) | map(lpad(5)) | join("");</ |
def printRows($m): _nwise($m) | map(lpad(5)) | join("");</syntaxhighlight> |
||
'''The task''' |
'''The task''' |
||
< |
<syntaxhighlight lang="jq">def isCurzon($n; $k): |
||
($k | power($n) + 1) % ($k * $n + 1) == 0; |
($k | power($n) + 1) % ($k * $n + 1) == 0; |
||
Line 384: | Line 1,026: | ||
""; |
""; |
||
printcurzons(2; 10; 1000)</ |
printcurzons(2; 10; 1000)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 415: | Line 1,057: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">isCurzon(n, k) = (BigInt(k)^n + 1) % (k * n + 1) == 0 |
||
function printcurzons(klow, khigh) |
function printcurzons(klow, khigh) |
||
Line 431: | Line 1,073: | ||
printcurzons(2, 10) |
printcurzons(2, 10) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
Curzon numbers with k = 2: |
Curzon numbers with k = 2: |
||
Line 453: | Line 1,095: | ||
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|Lambdatalk}}== |
|||
Using Javascript's BigInt. |
|||
<syntaxhighlight lang="scheme"> |
|||
{def is_curzon |
|||
{lambda {:n :k} |
|||
{= {BI.% {BI.+ {BI.** :k :n} 1} |
|||
{BI.+ {BI.* :k :n} 1} } 0}}} |
|||
-> is_curzon |
|||
{def curzon |
|||
{lambda {:length :base} |
|||
{S.replace \s by space in |
|||
{S.brmap {{lambda {:length :base :count :i} |
|||
{if {< {A.get 0 :count} :length} |
|||
then {if {is_curzon :i :base} |
|||
then {{lambda {:a :i} :i} |
|||
{A.set! 0 {+ {A.get 0 :count} 1} :count} :i} |
|||
else} |
|||
else _break_} |
|||
} :length :base {A.new 0}} |
|||
1 100000 1 }}}} |
|||
-> curzon |
|||
{S.map {lambda {:i} |
|||
{div {b First 50 Curzon numbers using a base of :i:} |
|||
{div {curzon 50 :i}}}} |
|||
{S.serie 2 10 2}} |
|||
-> |
|||
First 50 Curzon numbers using a base of 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 |
|||
First 50 Curzon numbers using a base of 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 |
|||
First 50 Curzon numbers using a base of 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 |
|||
First 50 Curzon numbers using a base of 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 |
|||
First 50 Curzon numbers using a base of 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 |
|||
{S.last {curzon 1000 6}} -> 20717 in 272193ms = 4.53655 minutes |
|||
</syntaxhighlight> |
|||
=={{header|Maxima}}== |
|||
<syntaxhighlight lang="maxima"> |
|||
/* Predicate function that checks wether a positive integer is generalized k-Curzon number or not */ |
|||
g_curzonp(n,k):=if mod((k^n)+1,k*n+1)=0 then true$ |
|||
/* Function that returns a list of the first len generalized k-Curzon numbers */ |
|||
g_curzon_count(len,k):=block( |
|||
[i:1,count:0,result:[]], |
|||
while count<len do (if g_curzonp(i,k) then (result:endcons(i,result),count:count+1),i:i+1), |
|||
result)$ |
|||
/* Test cases */ |
|||
g_curzon_count(50,2); |
|||
g_curzon_count(50,4); |
|||
g_curzon_count(50,6); |
|||
g_curzon_count(50,8); |
|||
g_curzon_count(50,10); |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[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] |
|||
[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] |
|||
[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] |
|||
[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] |
|||
[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] |
|||
</pre> |
|||
=={{header|Nim}}== |
|||
Nim standard library doesn’t provide a modular power, so we have to define our own function. |
|||
<syntaxhighlight lang="Nim">import std/strformat |
|||
func pow(a, n: Natural; m: Positive): Natural = |
|||
var a = a mod m |
|||
var n = n |
|||
if a > 0: |
|||
result = 1 |
|||
while n > 0: |
|||
if (n and 1) != 0: |
|||
result = (result * a) mod m |
|||
n = n shr 1 |
|||
a = (a * a) mod m |
|||
iterator curzonNumbers(k: Positive): Natural = |
|||
assert (k and 1) == 0, "base must be even." |
|||
var n = 1 |
|||
while true: |
|||
let m = k * n + 1 |
|||
if pow(k, n, m) + 1 == m: |
|||
yield n |
|||
inc n |
|||
### Task ### |
|||
for k in countup(2, 10, 2): |
|||
echo &"Curzon numbers for k = {k}:" |
|||
var count = 0 |
|||
for n in curzonNumbers(k): |
|||
inc count |
|||
stdout.write &"{n:>4}" |
|||
stdout.write if count mod 10 == 0: '\n' else: ' ' |
|||
if count == 50: break |
|||
echo() |
|||
### Stretch task ### |
|||
for k in countup(2, 10, 2): |
|||
var count = 0 |
|||
for n in curzonNumbers(k): |
|||
inc count |
|||
if count == 1000: |
|||
echo &"1000th Curzon number for k = {k:>2}: {n:>5}" |
|||
break |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Curzon numbers for k = 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 |
|||
Curzon numbers for k = 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 |
|||
Curzon numbers for k = 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 |
|||
Curzon numbers for k = 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 |
|||
Curzon numbers for k = 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 Curzon number for k = 2: 8646 |
|||
1000th Curzon number for k = 4: 9375 |
|||
1000th Curzon number for k = 6: 20717 |
|||
1000th Curzon number for k = 8: 22176 |
|||
1000th Curzon number for k = 10: 46845 |
|||
</pre> |
|||
=={{header|OCaml}}== |
|||
<syntaxhighlight lang="ocaml">let modpow m = |
|||
let rec loop p b e = |
|||
if e land 1 = 0 |
|||
then if e = 0 then p else loop p (b * b mod m) (e lsr 1) |
|||
else loop (p * b mod m) (b * b mod m) (e lsr 1) |
|||
in loop 1 |
|||
let is_curzon k n = |
|||
let r = k * n in r = modpow (succ r) k n |
|||
let () = |
|||
List.iter (fun x -> |
|||
Seq.(ints 0 |> filter (is_curzon x) |> take 50 |> map string_of_int) |
|||
|> List.of_seq |> String.concat " " |> Printf.printf "base %u:\n%s\n" x) |
|||
[2; 4; 6; 8; 10] |
|||
let () = |
|||
List.iter (fun x -> |
|||
Seq.(ints 0 |> filter (is_curzon x) |> drop 999 |> take 1 |
|||
|> iter (Printf.printf "base %u (1000th): %u\n" x))) |
|||
[2; 4; 6; 8; 10]</syntaxhighlight> |
|||
<pre> |
|||
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 |
|||
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 |
|||
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 |
|||
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 |
|||
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 |
|||
base 2 (1000th): 8646 |
|||
base 4 (1000th): 9375 |
|||
base 6 (1000th): 20717 |
|||
base 8 (1000th): 22176 |
|||
base 10 (1000th): 46845 |
|||
</pre> |
|||
=={{header|Odin}}== |
|||
<syntaxhighlight lang="Go"> |
|||
package curzon_numbers |
|||
/* imports */ |
|||
import "core:c/libc" |
|||
import "core:fmt" |
|||
/* main block */ |
|||
main :: proc() { |
|||
for k: int = 2; k <= 10; k += 2 { |
|||
fmt.println("\nCurzon numbers with base ", k) |
|||
count := 0 |
|||
n: int = 1 |
|||
for ; count < 50; n += 1 { |
|||
if is_curzon(n, k) { |
|||
count += 1 |
|||
libc.printf("%*d ", 4, n) |
|||
if (count) % 10 == 0 { |
|||
fmt.printf("\n") |
|||
} |
|||
} |
|||
} |
|||
for { |
|||
if is_curzon(n, k) { |
|||
count += 1} |
|||
if count == 1000 { |
|||
break} |
|||
n += 1 |
|||
} |
|||
libc.printf("1000th Curzon number with base %d: %d \n", k, n) |
|||
} |
|||
} |
|||
/* definitions */ |
|||
modpow :: proc(base, exp, mod: int) -> int { |
|||
if mod == 1 { |
|||
return 0} |
|||
result: int = 1 |
|||
base := base |
|||
exp := exp |
|||
base %= mod |
|||
for ; exp > 0; exp >>= 1 { |
|||
if ((exp & 1) == 1) { |
|||
result = (result * base) % mod} |
|||
base = (base * base) % mod |
|||
} |
|||
return result |
|||
} |
|||
is_curzon :: proc(n: int, k: int) -> bool { |
|||
r := k * n //const? |
|||
return modpow(k, n, r + 1) == r |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 Curzon number with base 2: 8646 |
|||
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 Curzon number with base 4: 9375 |
|||
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 Curzon number with base 6: 20717 |
|||
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 Curzon number with base 8: 22176 |
|||
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 Curzon number with base 10: 46845 |
|||
</pre> |
</pre> |
||
Line 459: | Line 1,397: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="pascal"> |
||
program CurzonNumbers; |
program CurzonNumbers; |
||
uses SysUtils; |
uses SysUtils; |
||
Line 528: | Line 1,466: | ||
ListCurzonNumbers(11); |
ListCurzonNumbers(11); |
||
end. |
end. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 589: | Line 1,527: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[CurzonNumberQ] |
||
CurzonNumberQ[b_Integer][n_Integer]:=PowerMod[b,n,b n+1]==b n |
CurzonNumberQ[b_Integer][n_Integer]:=PowerMod[b,n,b n+1]==b n |
||
val=Select[Range[100000],CurzonNumberQ[2]]; |
val=Select[Range[100000],CurzonNumberQ[2]]; |
||
Line 609: | Line 1,547: | ||
val=Select[Range[100000],CurzonNumberQ[10]]; |
val=Select[Range[100000],CurzonNumberQ[10]]; |
||
Take[val,50] |
Take[val,50] |
||
val[[1000]]</ |
val[[1000]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{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} |
<pre>{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} |
||
Line 630: | Line 1,568: | ||
46845</pre> |
46845</pre> |
||
=={{header|PARI/GP}}== |
|||
{{trans|Mathematica/Wolfram_Language}} |
|||
<syntaxhighlight lang="PARI/GP"> |
|||
/* Define the CurzonNumberQ function for base b */ |
|||
powermod(a,k,n)=lift(Mod(a,n)^k) |
|||
CurzonNumberQ(b, n) = (powermod(b,n,b*n+1)== b*n); |
|||
/* Define a function to find Curzon numbers within a range for base b */ |
|||
FindCurzonNumbers(b, maxrange) = { |
|||
local(val, res, i); |
|||
val = vector(maxrange); |
|||
res = []; |
|||
for(i = 1, maxrange, |
|||
if(CurzonNumberQ(b, i), res = concat(res, i)); |
|||
); |
|||
return(Vec(res)); |
|||
} |
|||
/* Select and display the first 50 Curzon numbers and the 1000th for base 2 */ |
|||
val = FindCurzonNumbers(2, 100000); |
|||
print(vector(50, i, val[i])); /* First 50 */ |
|||
print(val[1000]); /* 1000th Curzon number */ |
|||
/* Select and display for base 4 */ |
|||
val = FindCurzonNumbers(4, 100000); |
|||
print(vector(50, i, val[i])); /* First 50 */ |
|||
print(val[1000]); /* 1000th Curzon number */ |
|||
/* Select and display for base 6 */ |
|||
val = FindCurzonNumbers(6, 100000); |
|||
print(vector(50, i, val[i])); /* First 50 */ |
|||
print(val[1000]); /* 1000th Curzon number */ |
|||
/* Select and display for base 8 */ |
|||
val = FindCurzonNumbers(8, 100000); |
|||
print(vector(50, i, val[i])); /* First 50 */ |
|||
print(val[1000]); /* 1000th Curzon number */ |
|||
/* Select and display for base 10 */ |
|||
val = FindCurzonNumbers(10, 100000); |
|||
print(vector(50, i, val[i])); /* First 50 */ |
|||
print(val[1000]); /* 1000th Curzon number */ |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[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] |
|||
8646 |
|||
[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] |
|||
9375 |
|||
[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] |
|||
20717 |
|||
[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] |
|||
22176 |
|||
[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] |
|||
46845 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
|||
<lang perl>use strict; |
|||
<syntaxhighlight lang="perl">use strict; |
|||
use warnings; |
use warnings; |
||
use |
use ntheory 'powmod'; |
||
sub curzon { |
sub curzon { |
||
Line 640: | Line 1,636: | ||
my($n,@C) = 0; |
my($n,@C) = 0; |
||
while (++$n) { |
while (++$n) { |
||
my $r = $base * $n; |
|||
push @C, $n if powmod($base, $n, $r + 1) == $r; |
|||
return @C if $cnt == @C; |
return @C if $cnt == @C; |
||
} |
} |
||
Line 647: | Line 1,644: | ||
my $upto = 50; |
my $upto = 50; |
||
for my $k (<2 4 6 8 10>) { |
for my $k (<2 4 6 8 10>) { |
||
my @C = curzon |
my @C = curzon $k, 1000; |
||
print "First $upto Curzon numbers using a base of $k:\n" . |
print "First $upto Curzon numbers using a base of $k:\n" . |
||
(sprintf "@{['%5d' x $upto]}", @C[0..$upto-1]) =~ s/ |
(sprintf "@{['%5d' x $upto]}", @C[0..$upto-1]) =~ s/.{100}/$&\n/gr; |
||
printf "%50s\n\n", "Thousandth: $C[-1]" |
|||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
|||
<pre>First 50 Curzon numbers using a base of 2: |
|||
First 50 Curzon numbers using a base of 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 |
|||
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 |
|||
Thousandth: 8646 |
|||
194 198 209 210 221 230 233 245 249 254 Thousandth: 8646 |
|||
First 50 Curzon numbers using a base of 4: |
First 50 Curzon numbers using a base of 4: |
||
1 3 7 9 13 15 25 27 37 39 43 45 49 57 67 69 73 79 87 93 |
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 Thousandth: 9375 |
|||
Thousandth: 9375 |
|||
First 50 Curzon numbers using a base of 6: |
First 50 Curzon numbers using a base of 6: |
||
1 6 30 58 70 73 90 101 105 121 125 146 153 166 170 181 182 185 210 233 |
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 Thousandth: 20717 |
|||
Thousandth: 20717 |
|||
First 50 Curzon numbers using a base of 8: |
First 50 Curzon numbers using a base of 8: |
||
1 14 35 44 72 74 77 129 131 137 144 149 150 185 200 219 236 266 284 285 |
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 Thousandth: 22176 |
|||
Thousandth: 22176 |
|||
First 50 Curzon numbers using a base of 10: |
First 50 Curzon numbers using a base of 10: |
||
1 9 10 25 106 145 190 193 238 253 306 318 349 385 402 462 486 526 610 649 |
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 Thousandth: 46845 |
|||
Thousandth: 46845</pre> |
|||
</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 703: | Line 1,702: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 730: | Line 1,729: | ||
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 |
||
One thousandth: 46845 |
One thousandth: 46845 |
||
</pre> |
|||
=={{header|Python}}== |
|||
<syntaxhighlight lang="python">def is_Curzon(n, k): |
|||
r = k * n |
|||
return pow(k, n, r + 1) == r |
|||
for k in [2, 4, 6, 8, 10]: |
|||
n, curzons = 1, [] |
|||
while len(curzons) < 1000: |
|||
if is_Curzon(n, k): |
|||
curzons.append(n) |
|||
n += 1 |
|||
print(f'Curzon numbers with k = {k}:') |
|||
for i, c in enumerate(curzons[:50]): |
|||
print(f'{c: 5,}', end='\n' if (i + 1) % 25 == 0 else '') |
|||
print(f' Thousandth Curzon with k = {k}: {curzons[999]}.\n')</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 2: 8646. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 4: 9375. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 6: 20717. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 8: 22176. |
|||
Curzon numbers with k = 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 1,033 1,077 1,125 1,126 1,141 1,149 1,230 1,405 1,422 1,441 1,485 1,509 1,510 1,513 1,606 1,614 1,630 1,665 1,681 1,690 1,702 1,785 1,837 |
|||
Thousandth Curzon with k = 10: 46845. |
|||
</pre> |
</pre> |
||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
< |
<syntaxhighlight lang="quackery"> [ number$ |
||
space 4 of swap join |
space 4 of swap join |
||
-5 split nip echo$ ] is rjust ( n --> ) |
-5 split nip echo$ ] is rjust ( n --> ) |
||
Line 766: | Line 1,808: | ||
say " ... " |
say " ... " |
||
-1 peek echo cr cr ] |
-1 peek echo cr cr ] |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 812: | Line 1,854: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>sub curzon ($base) { lazy (1..∞).hyper.map: { $_ if (exp($_, $base) + 1) %% ($base × $_ + 1) } }; |
||
for <2 4 6 8 10> { |
for <2 4 6 8 10> { |
||
my $curzon = .&curzon; |
my $curzon = .&curzon; |
||
say "\nFirst 50 Curzon numbers using a base of $_:\n" ~ |
say "\nFirst 50 Curzon numbers using a base of $_:\n" ~ |
||
$curzon[^50].batch( |
$curzon[^50].batch(10)».fmt("%4s").join("\n") ~ |
||
"\nOne thousandth: " ~ $curzon[999] |
"\nOne thousandth: " ~ $curzon[999] |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 50 Curzon numbers using a base of 2: |
<pre>First 50 Curzon numbers using a base of 2: |
||
1 2 5 6 9 14 18 21 26 29 |
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 |
|||
One thousandth: 8646 |
One thousandth: 8646 |
||
First 50 Curzon numbers using a base of 4: |
First 50 Curzon numbers using a base of 4: |
||
1 3 7 9 13 15 25 27 37 39 |
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 |
|||
One thousandth: 9375 |
One thousandth: 9375 |
||
First 50 Curzon numbers using a base of 6: |
First 50 Curzon numbers using a base of 6: |
||
1 6 30 58 70 73 90 101 105 121 |
1 6 30 58 70 73 90 101 105 121 |
||
125 146 153 166 170 181 182 185 210 233 |
|||
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 |
|||
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 |
|||
One thousandth: 20717 |
One thousandth: 20717 |
||
First 50 Curzon numbers using a base of 8: |
First 50 Curzon numbers using a base of 8: |
||
1 14 35 44 72 74 77 129 131 137 |
1 14 35 44 72 74 77 129 131 137 |
||
144 149 150 185 200 219 236 266 284 285 |
|||
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 |
|||
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 |
|||
One thousandth: 22176 |
One thousandth: 22176 |
||
First 50 Curzon numbers using a base of 10: |
First 50 Curzon numbers using a base of 10: |
||
1 9 10 25 106 145 190 193 238 253 |
1 9 10 25 106 145 190 193 238 253 |
||
306 318 349 385 402 462 486 526 610 649 |
|||
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 |
|||
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 |
|||
One thousandth: 46845</pre> |
One thousandth: 46845</pre> |
||
=={{header|RPL}}== |
|||
{{works with|Halcyon Calc|4.2.7}} |
|||
{| class="wikitable" |
|||
! Code |
|||
! Comments |
|||
|- |
|||
| |
|||
≪ → x n m |
|||
≪ '''IF''' OVER |
|||
'''THEN''' 1 1 n '''START''' x * m MOD '''NEXT''' |
|||
'''ELSE''' 1 '''END''' |
|||
≫ ≫ 'XnMOD' STO |
|||
≪ → k |
|||
≪ {} 1 '''WHILE''' OVER SIZE 50 < '''REPEAT''' |
|||
k OVER * 1 + |
|||
DUP2 k ROT ROT XnMOD 1 + SWAP MOD |
|||
'''IF''' NOT '''THEN''' SWAP OVER + SWAP '''END''' |
|||
1 + |
|||
'''END''' DROP |
|||
≫ ≫ 'QRZ50' STO |
|||
| |
|||
''( x n m -- (x^n mod m) )'' |
|||
If n<>0... |
|||
then x^n mod m = (((x mod m) * x mod m) ... * x mod m) |
|||
else x^0 mod m = 1 |
|||
''( k -- { 50 Curzon numbers } )'' |
|||
Initialize |
|||
Get k*n + 1 |
|||
Get k^n+1 mod k*n+1 |
|||
If zero then add it to sequence |
|||
Increment n |
|||
|} |
|||
The following line of code delivers what is required: |
|||
2 QRZ50 10 QRZ50 |
|||
{{out}} |
|||
<pre> |
|||
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 } |
|||
1: { 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 } |
|||
</pre> |
|||
=={{header|Ruby}}== |
|||
<syntaxhighlight lang="ruby">def curzons(k) |
|||
Enumerator.new do |y| |
|||
(1..).each do |n| |
|||
r = k * n |
|||
y << n if k.pow(n, r + 1) == r |
|||
end |
|||
end |
|||
end |
|||
[2,4,6,8,10].each do |base| |
|||
puts "Curzon numbers with k = #{base}:" |
|||
puts curzons(base).take(50).join(", ") |
|||
puts "Thousandth Curzon with k = #{base}: #{curzons(base).find.each.with_index(1){|_,i| i == 1000} }","" |
|||
end</syntaxhighlight> |
|||
{{out}}<pre>Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 2: 8646. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 4: 9375. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 6: 20717. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 8: 22176. |
|||
Curzon numbers with k = 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 |
|||
Thousandth Curzon with k = 10: 46845. |
|||
</pre> |
|||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
<syntaxhighlight lang="rust">fn modpow(mut base: usize, mut exp: usize, n: usize) -> usize { |
|||
<lang rust>// [dependencies] |
|||
if n == 1 { |
|||
return 0; |
|||
} |
|||
let mut result = 1; |
|||
base %= n; |
|||
while exp > 0 { |
|||
if (exp & 1) == 1 { |
|||
result = (result * base) % n; |
|||
} |
|||
base = (base * base) % n; |
|||
exp >>= 1; |
|||
} |
|||
result |
|||
} |
|||
fn is_curzon(n: usize, k: usize) -> bool { |
|||
let m = k * n + 1; |
|||
modpow(k, n, m) + 1 == m |
|||
fn is_curzon(n: u32, k: u32) -> bool { |
|||
use rug::{Complete, Integer}; |
|||
(Integer::u_pow_u(k, n).complete() + 1) % (k * n + 1) == 0 |
|||
} |
} |
||
Line 878: | Line 2,031: | ||
println!("1000th Curzon number with base {k}: {n}\n"); |
println!("1000th Curzon number with base {k}: {n}\n"); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 925: | Line 2,078: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func is_curzon(n, k) { |
||
powmod(k, n, k*n + 1).is_congruent(-1, k*n + 1) && (n > 0) |
powmod(k, n, k*n + 1).is_congruent(-1, k*n + 1) && (n > 0) |
||
} |
} |
||
Line 933: | Line 2,086: | ||
say 50.by {|n| is_curzon(n, k) }.join(' ') |
say 50.by {|n| is_curzon(n, k) }.join(' ') |
||
say ("1000th term: ", 1000.th {|n| is_curzon(n,k) }) |
say ("1000th term: ", 1000.th {|n| is_curzon(n,k) }) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 956: | Line 2,109: | ||
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 |
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 term: 46845 |
1000th term: 46845 |
||
</pre> |
|||
=={{header|V (Vlang)}}== |
|||
{{trans|go}} |
|||
<syntaxhighlight lang="v (vlang)">import math.big |
|||
fn main() { |
|||
zero := big.zero_int |
|||
one := big.one_int |
|||
for k := i64(2); k <= 10; k += 2 { |
|||
bk := big.integer_from_i64(k) |
|||
println("The first 50 Curzon numbers using a base of $k:") |
|||
mut count := 0 |
|||
mut n := i64(1) |
|||
mut pow := big.integer_from_i64(k) |
|||
mut curzon50 := []i64{} |
|||
for { |
|||
z := pow + one |
|||
d := k*n + 1 |
|||
bd := big.integer_from_i64(d) |
|||
if z%bd == zero { |
|||
if count < 50 { |
|||
curzon50 << n |
|||
} |
|||
count++ |
|||
if count == 50 { |
|||
for i in 0..curzon50.len { |
|||
print("${curzon50[i]:4} ") |
|||
if (i+1)%10 == 0 { |
|||
println('') |
|||
} |
|||
} |
|||
print("\nOne thousandth: ") |
|||
} |
|||
if count == 1000 { |
|||
println(n) |
|||
break |
|||
} |
|||
} |
|||
n++ |
|||
pow *= bk |
|||
} |
|||
println('') |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 8646 |
|||
The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 9375 |
|||
The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 20717 |
|||
The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 22176 |
|||
The first 50 Curzon numbers using a base of 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 |
|||
One thousandth: 46845 |
|||
</pre> |
</pre> |
||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
===Version 1 (Embedded using GMP)=== |
|||
{{libheader|Wren-gmp}} |
{{libheader|Wren-gmp}} |
||
{{libheader|Wren-seq}} |
|||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="wren">/* Curzon_numbers.wren */ |
||
import "./gmp" for Mpz |
import "./gmp" for Mpz |
||
import "./seq" for Lst |
|||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 981: | Line 2,225: | ||
count = count + 1 |
count = count + 1 |
||
if (count == 50) { |
if (count == 50) { |
||
Fmt.tprint("$4d", curzon50, 10) |
|||
System.write("\nOne thousandth: ") |
System.write("\nOne thousandth: ") |
||
} |
} |
||
if (count == 1000) { |
if (count == 1000) { |
||
Fmt.print("$,d", n) |
|||
break |
break |
||
} |
} |
||
Line 993: | Line 2,237: | ||
} |
} |
||
System.print() |
System.print() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
The first 50 Curzon numbers using a base of 2: |
The first 50 Curzon numbers using a base of 2: |
||
1 2 5 6 9 14 18 21 26 29 |
1 2 5 6 9 14 18 21 26 29 |
||
30 33 41 50 53 54 65 69 74 78 |
30 33 41 50 53 54 65 69 74 78 |
||
81 86 89 90 98 105 113 114 125 134 |
81 86 89 90 98 105 113 114 125 134 |
||
138 141 146 153 158 165 173 174 186 189 |
138 141 146 153 158 165 173 174 186 189 |
||
194 198 209 210 221 230 233 245 249 254 |
194 198 209 210 221 230 233 245 249 254 |
||
One thousandth: |
One thousandth: 8,646 |
||
The first 50 Curzon numbers using a base of 4: |
The first 50 Curzon numbers using a base of 4: |
||
1 3 7 9 13 15 25 27 37 39 |
1 3 7 9 13 15 25 27 37 39 |
||
43 45 49 57 67 69 73 79 87 93 |
43 45 49 57 67 69 73 79 87 93 |
||
97 99 105 115 127 135 139 153 163 165 |
97 99 105 115 127 135 139 153 163 165 |
||
169 175 177 183 189 193 199 205 207 213 |
169 175 177 183 189 193 199 205 207 213 |
||
219 235 249 253 255 265 267 273 277 279 |
219 235 249 253 255 265 267 273 277 279 |
||
One thousandth: |
One thousandth: 9,375 |
||
The first 50 Curzon numbers using a base of 6: |
The first 50 Curzon numbers using a base of 6: |
||
1 6 30 58 70 73 90 101 105 121 |
1 6 30 58 70 73 90 101 105 121 |
||
125 146 153 166 170 181 182 185 210 233 |
125 146 153 166 170 181 182 185 210 233 |
||
241 242 266 282 290 322 373 381 385 390 |
241 242 266 282 290 322 373 381 385 390 |
||
397 441 445 446 450 453 530 557 562 585 |
397 441 445 446 450 453 530 557 562 585 |
||
593 601 602 605 606 621 646 653 670 685 |
593 601 602 605 606 621 646 653 670 685 |
||
One thousandth: |
One thousandth: 20,717 |
||
The first 50 Curzon numbers using a base of 8: |
The first 50 Curzon numbers using a base of 8: |
||
1 14 35 44 72 74 77 129 131 137 |
1 14 35 44 72 74 77 129 131 137 |
||
144 149 150 185 200 219 236 266 284 285 |
144 149 150 185 200 219 236 266 284 285 |
||
299 309 336 357 381 386 390 392 402 414 |
299 309 336 357 381 386 390 392 402 414 |
||
420 441 455 459 470 479 500 519 527 536 |
420 441 455 459 470 479 500 519 527 536 |
||
557 582 600 602 617 639 654 674 696 735 |
557 582 600 602 617 639 654 674 696 735 |
||
One thousandth: |
One thousandth: 22,176 |
||
The first 50 Curzon numbers using a base of 10: |
The first 50 Curzon numbers using a base of 10: |
||
1 9 10 25 106 145 190 193 238 253 |
1 9 10 25 106 145 190 193 238 253 |
||
306 318 349 385 402 462 486 526 610 649 |
306 318 349 385 402 462 486 526 610 649 |
||
658 678 733 762 810 990 994 1033 1077 1125 |
658 678 733 762 810 990 994 1033 1077 1125 |
||
1126 1141 1149 1230 1405 1422 1441 1485 1509 1510 |
1126 1141 1149 1230 1405 1422 1441 1485 1509 1510 |
||
1513 1606 1614 1630 1665 1681 1690 1702 1785 1837 |
1513 1606 1614 1630 1665 1681 1690 1702 1785 1837 |
||
One thousandth: |
One thousandth: 46,845 |
||
</pre> |
|||
===Version 2 (Wren-cli)=== |
|||
{{trans|C++}} |
|||
{{libheader|Wren-math}} |
|||
Alternatively, using ''Int.modPow'' rather than ''GMP'' so it will run on Wren-cli, albeit about 6 times more slowly. |
|||
<syntaxhighlight lang="wren">import "./math" for Int |
|||
import "./fmt" for Fmt |
|||
var isCurzon = Fn.new { |n, k| |
|||
var r = k * n |
|||
return Int.modPow(k, n, r+1) == r |
|||
} |
|||
var k = 2 |
|||
while (k <= 10) { |
|||
System.print("Curzon numbers with base %(k):") |
|||
var n = 1 |
|||
var count = 0 |
|||
while (count < 50) { |
|||
if (isCurzon.call(n, k)) { |
|||
Fmt.write("$4d ", n) |
|||
count = count + 1 |
|||
if (count % 10 == 0) System.print() |
|||
} |
|||
n = n + 1 |
|||
} |
|||
while (true) { |
|||
if (isCurzon.call(n, k)) count = count + 1 |
|||
if (count == 1000) break |
|||
n = n + 1 |
|||
} |
|||
Fmt.print("1,000th Curzon number with base $d: $,d\n", k, n) |
|||
k = k + 2 |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
As Version 1. |
|||
</pre> |
|||
=={{header|XPL0}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang "XPL0">func ModPow(Base, Exp, Mod); |
|||
int Base, Exp, Mod, Result; |
|||
[if Mod = 1 then return 0; |
|||
Result:= 1; |
|||
Base:= rem(Base/Mod); |
|||
while Exp > 0 do |
|||
[if (Exp&1) = 1 then Result:= rem((Result*Base)/Mod); |
|||
Base:= rem((Base*Base) / Mod); |
|||
Exp:= Exp >> 1; |
|||
]; |
|||
return Result; |
|||
]; |
|||
func IsCurzon(N, K); |
|||
int N, K, R; |
|||
[R:= K * N; |
|||
return ModPow(K, N, R+1) = R; |
|||
]; |
|||
int K, N, Count; |
|||
[K:= 2; |
|||
Format(5, 0); |
|||
while K <= 10 do |
|||
[Text(0, "Curzon numbers with base "); IntOut(0, K); CrLf(0); |
|||
N:= 1; Count:= 0; |
|||
while Count < 50 do |
|||
[if IsCurzon(N, K) then |
|||
[RlOut(0, float(N)); |
|||
Count:= Count+1; |
|||
if rem(Count/10) = 0 then CrLf(0); |
|||
]; |
|||
N:= N+1; |
|||
]; |
|||
K:= K+2; |
|||
]; |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
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 |
|||
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 |
|||
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 |
|||
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 |
|||
</pre> |
</pre> |
Latest revision as of 18:29, 29 March 2024
A Curzon number is defined to be a positive integer n for which 2n + 1 is evenly divisible by 2 × n + 1.
You are encouraged to solve this task according to the task description, using any language you may know.
Generalized Curzon numbers are those where the positive integer n, using a base integer k, satisfy the condition that kn + 1 is evenly divisible by k × n + 1.
Base here does not imply the radix of the counting system; rather the integer the equation is based on. All calculations should be done in base 10.
Generalized Curzon numbers only exist for even base integers.
- Task
- Find and show the first 50 Generalized Curzon numbers for even base integers from 2 through 10.
- Stretch
- Find and show the one thousandth.
- See also
and even though it is not specifically mentioned that they are Curzon numbers:
- OEIS:A230076 - (A007521(n)-1)/4 (Generalized Curzon numbers with a base 4)
11l
F is_curzon(n, k)
V m = k * n + 1
R pow(Int64(k), n, m) + 1 == m
L(k) [2, 4, 6, 8, 10]
V n = 1
[Int] curzons
L curzons.len < 1000
I is_curzon(n, k)
curzons.append(n)
n++
print(‘Curzon numbers with k = ’k‘:’)
L(c) curzons[0.<50]
V i = L.index
print(f:‘{commatize(c):6}’, end' I (i + 1) % 25 == 0 {"\n"} E ‘’)
print(‘ Thousandth Curzon with k = ’k‘: ’curzons[999]".\n")
- Output:
Curzon numbers with k = 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 Thousandth Curzon with k = 2: 8646. Curzon numbers with k = 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 Thousandth Curzon with k = 4: 9375. Curzon numbers with k = 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 Thousandth Curzon with k = 6: 20717. Curzon numbers with k = 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 Thousandth Curzon with k = 8: 22176. Curzon numbers with k = 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 1,033 1,077 1,125 1,126 1,141 1,149 1,230 1,405 1,422 1,441 1,485 1,509 1,510 1,513 1,606 1,614 1,630 1,665 1,681 1,690 1,702 1,785 1,837 Thousandth Curzon with k = 10: 46845.
ALGOL 68
BEGIN # find some generalised Curzon numbers - translation of the C++ sample #
PROC modpow = ( LONG INT rqd base, rqd exp, mod )LONG INT:
IF mod = 1
THEN 0
ELSE
LONG INT result := 1;
LONG INT base := rqd base MOD mod;
LONG INT exp := rqd exp;
WHILE exp > 0 DO
IF ODD exp THEN
result TIMESAB base MODAB mod
FI;
base TIMESAB base MODAB mod;
exp OVERAB 2
OD;
result
FI # modpow # ;
PROC is curzon = ( LONG INT n, k )BOOL:
BEGIN
LONG INT m = k * n + 1;
modpow( k, n, m ) + 1 = m
END # is curon # ;
FOR k FROM 2 BY 2 TO 10 DO
print( ( "Curzon numbers with base ", whole( k, 0 ), ":", newline ) );
INT count := 0, n := 0;
WHILE n +:= 1;
count < 50
DO
IF is curzon( n, k ) THEN
print( ( whole( n, -4 )
, IF ( count +:= 1 ) MOD 10 = 0 THEN newline ELSE " " FI
)
)
FI
OD;
WHILE IF is curzon( n, k ) THEN count +:= 1 FI;
count < 1000
DO
n +:= 1
OD;
print( ( "1000th Curzon number with base ", whole( k, 0 ), ": ", whole( n, 0 ) ) );
print( ( newline, newline ) )
OD
END
- Output:
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 Curzon number with base 2: 8646 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 Curzon number with base 4: 9375 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 Curzon number with base 6: 20717 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 Curzon number with base 8: 22176 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 Curzon number with base 10: 46845
Arturo
curzon?: function [n,base]->
zero? (inc base^n) % inc base*n
first50: function [b][
result: new []
i: 1
while [50 > size result][
if curzon? i b -> 'result ++ i
i: i + 1
]
return result
]
oneThousandth: function [b][
cnt: 0
i: 1
while [cnt < 1000][
if curzon? i b -> cnt: cnt+1
i: i + 1
]
return dec i
]
loop select 2..10 => even? 'withBase [
print ["First 50 Curzon numbers with base" withBase]
loop split.every: 10 first50 withBase 'row [
print map to [:string] row 'item -> pad item 4
]
print ["\n1000th Curzon with base" withBase "=" oneThousandth withBase]
print ""
]
- Output:
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 Curzon with base 2 = 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 Curzon with base 4 = 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 Curzon with base 6 = 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 Curzon with base 8 = 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 Curzon with base 10 = 46845
C
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <locale.h>
uint64_t modPow(uint64_t base, uint64_t exp, uint64_t mod) {
if (mod == 1) return 0;
uint64_t result = 1;
base %= mod;
for (; exp > 0; exp >>= 1) {
if ((exp & 1) == 1) result = (result * base) % mod;
base = (base * base) % mod;
}
return result;
}
bool isCurzon(uint64_t n, uint64_t k) {
const uint64_t r = k * n;
return modPow(k, n, r+1) == r;
}
int main() {
uint64_t k, n, count;
setlocale(LC_NUMERIC, "");
for (k = 2; k <= 10; k += 2) {
printf("Curzon numbers with base %ld:\n", k);
for (n = 1, count = 0; count < 50; ++n) {
if (isCurzon(n, k)) {
printf("%4ld ", n);
if (++count % 10 == 0) printf("\n");
}
}
for (;;) {
if (isCurzon(n, k)) ++count;
if (count == 1000) break;
++n;
}
printf("1,000th Curzon number with base %ld: %'ld\n\n", k, n);
}
return 0;
}
- Output:
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 1,000th Curzon number with base 2: 8,646 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 1,000th Curzon number with base 4: 9,375 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 1,000th Curzon number with base 6: 20,717 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 1,000th Curzon number with base 8: 22,176 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 1,000th Curzon number with base 10: 46,845
C++
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
uint64_t modpow(uint64_t base, uint64_t exp, uint64_t mod) {
if (mod == 1)
return 0;
uint64_t result = 1;
base %= mod;
for (; exp > 0; exp >>= 1) {
if ((exp & 1) == 1)
result = (result * base) % mod;
base = (base * base) % mod;
}
return result;
}
bool is_curzon(uint64_t n, uint64_t k) {
const uint64_t r = k * n;
return modpow(k, n, r + 1) == r;
}
int main() {
for (uint64_t k = 2; k <= 10; k += 2) {
std::cout << "Curzon numbers with base " << k << ":\n";
uint64_t count = 0, n = 1;
for (; count < 50; ++n) {
if (is_curzon(n, k)) {
std::cout << std::setw(4) << n
<< (++count % 10 == 0 ? '\n' : ' ');
}
}
for (;;) {
if (is_curzon(n, k))
++count;
if (count == 1000)
break;
++n;
}
std::cout << "1000th Curzon number with base " << k << ": " << n
<< "\n\n";
}
return 0;
}
- Output:
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 Curzon number with base 2: 8646 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 Curzon number with base 4: 9375 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 Curzon number with base 6: 20717 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 Curzon number with base 8: 22176 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 Curzon number with base 10: 46845
EasyLang
func pow_mod b power modulus .
x = 1
while power > 0
if power mod 2 = 1
x = x * b mod modulus
.
b = b * b mod modulus
power = power div 2
.
return x
.
for k = 2 step 2 to 10
numfmt 0 0
print "First 50 Curzon numbers using a base of " & k & ":"
numfmt 0 4
n = 1
count = 0
repeat
m = k * n + 1
p = pow_mod k n m + 1
if p = m
count += 1
if count <= 50
write " " & n
if count mod 9 = 0
print ""
.
.
.
until count = 1000
n += 1
.
print "" ; print "One thousandth: " & n
print ""
.
Factor
USING: grouping interpolate io kernel make math math.functions
prettyprint ranges sequences ;
: curzon? ( k n -- ? ) [ ^ 1 + ] 2keep * 1 + divisor? ;
: next ( k n -- k n' ) [ 2dup curzon? ] [ 1 + ] do until ;
: curzon ( k -- seq )
1 [ 50 [ dup , next ] times ] { } make 2nip ;
: curzon. ( k -- )
dup [I Curzon numbers with base ${}:I] nl
curzon 10 group simple-table. ;
2 10 2 <range> [ curzon. nl ] each
- Output:
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 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 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 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 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
FreeBASIC
Normal basic
' limit: k * n +1 must be smaller then 2^32-1
Function pow_mod(b As ULongInt, power As ULongInt, modulus As ULongInt) As ULongInt
' returns b ^ power mod modulus
Dim As ULongInt x = 1
While power > 0
If (power And 1) = 1 Then
x = (x * b) Mod modulus
End If
b = (b * b) Mod modulus
power = power Shr 1
Wend
Return x
End Function
For k As ULongInt= 2 To 10 Step 2
Print "The first 50 Curzon numbers using a base of "; k; ":"
Dim As ULongInt count, n = 1, p, m
Do
m = k * n +1
p = pow_mod(k, n ,m) +1
If p = m Then
count += 1
If count <= 50 Then
Print Using "#####"; n;
If (count Mod 10) = 0 Then Print
ElseIf count = 1000 Then
Print : Print "One thousandth: "; n
Print : Print
Exit Do
End If
End If
n += 1
Loop
Next
Sleep
- Output:
The first 50 Curzon numbers using a base of 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 254One thousandth: 8646
The first 50 Curzon numbers using a base of 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 279One thousandth: 9375
The first 50 Curzon numbers using a base of 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 685One thousandth: 20717
The first 50 Curzon numbers using a base of 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 735One thousandth: 22176
The first 50 Curzon numbers using a base of 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 1837One thousandth: 46845
GMP version
#include once "gmp.bi"
Dim As Longint t = Len(__mpz_struct)
Dim As mpz_ptr pow = Allocate(t)
Dim As mpz_ptr z = Allocate(t)
mpz_init(pow): mpz_init(z)
For k As Uinteger = 2 To 10 Step 2
Print "The first 50 Curzon numbers using a base of"; k; ":"
Dim As Integer count = 0, n = 1
mpz_set_si(pow,k)
Do
mpz_add_ui(z,pow,1)
Dim As Integer d = k*n + 1
If mpz_divisible_ui_p(z,d) Then
count += 1
If count <= 50 Then
Print Using "#####"; n
If (count Mod 25) = 0 Then Print
Elseif count=1000 Then
Print "One thousandth: "; n
Print : Print
Exit Do
End If
End If
n += 1
mpz_mul_si(pow,pow,k)
Loop
Next k
Sleep
Go
Based on Version 1.
package main
import (
"fmt"
"math/big"
)
func main() {
zero := big.NewInt(0)
one := big.NewInt(1)
for k := int64(2); k <= 10; k += 2 {
bk := big.NewInt(k)
fmt.Println("The first 50 Curzon numbers using a base of", k, ":")
count := 0
n := int64(1)
pow := big.NewInt(k)
z := new(big.Int)
var curzon50 []int64
for {
z.Add(pow, one)
d := k*n + 1
bd := big.NewInt(d)
if z.Rem(z, bd).Cmp(zero) == 0 {
if count < 50 {
curzon50 = append(curzon50, n)
}
count++
if count == 50 {
for i := 0; i < len(curzon50); i++ {
fmt.Printf("%4d ", curzon50[i])
if (i+1)%10 == 0 {
fmt.Println()
}
}
fmt.Print("\nOne thousandth: ")
}
if count == 1000 {
fmt.Println(n)
break
}
}
n++
pow.Mul(pow, bk)
}
fmt.Println()
}
}
- Output:
The first 50 Curzon numbers using a base of 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 One thousandth: 8646 The first 50 Curzon numbers using a base of 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 One thousandth: 9375 The first 50 Curzon numbers using a base of 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 One thousandth: 20717 The first 50 Curzon numbers using a base of 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 One thousandth: 22176 The first 50 Curzon numbers using a base of 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 One thousandth: 46845
Haskell
import Data.List.Split ( chunksOf )
isGeneralizedCurzon :: Integer -> Integer -> Bool
isGeneralizedCurzon base n = mod ( base ^ n + 1 ) ( base * n + 1 ) == 0
solution :: Integer -> [Integer]
solution base = take 50 $ filter (\i -> isGeneralizedCurzon base i ) [1..]
printChunk :: [Integer] -> String
printChunk chunk = foldl1 (++) $ map (\i -> (take ( 4 - (length $ show i) )
$ repeat ' ' ) ++ show i ++ " ") chunk
prettyPrint :: [Integer] -> [String]
prettyPrint list = map printChunk $ chunksOf 10 list
oneThousandth :: Integer -> Integer
oneThousandth base = last $ take 950 $ filter (\i -> isGeneralizedCurzon base i )
[(last $ solution base) + 1 ..]
printBlock :: Integer -> [String]
printBlock base = ["first 50 Curzon numbers using a base of " ++ show base ++ " :"]
++ (prettyPrint $ solution base) ++ ["one thousandth at base " ++ show base ++
": " ++ (show $ oneThousandth base)] ++ [take 50 $ repeat '-']
main :: IO ( )
main = do
blocks <- return $ concat $ map (\i -> printBlock i ) [2 , 4 , 6 , 8 , 10]
mapM_ putStrLn blocks
- Output:
first 50 Curzon numbers using a base of 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 one thousandth at base 2: 8646 -------------------------------------------------- first 50 Curzon numbers using a base of 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 one thousandth at base 4: 9375 -------------------------------------------------- first 50 Curzon numbers using a base of 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 one thousandth at base 6: 20717 -------------------------------------------------- first 50 Curzon numbers using a base of 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 one thousandth at base 8: 22176 -------------------------------------------------- first 50 Curzon numbers using a base of 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 one thousandth at base 10: 46845 --------------------------------------------------
J
A simple test for whether a number is a (generalized) Curzon number is:
isCurzon =: 2&$: : (0 = * |&:>: ^)
Here, the monadic case uses 2 as the left argument for the dyadic case, which handles generalized Curzon numbers.
However, this is inefficient for large numbers, due to it explicitly exponentiating. Since we test the remainder immediately after, we can use a special combination instead,
modpow =: {{ m&|@^ }}
isCurzon =: {{
z =: >: x * y
z = >: x z modpow y
}}
This avoids performing the large exponentiation, which is significantly faster. For generating the results:
generateCurzons =: {{
found =. i. 0x
current =. 0x
while. 1000 > # found do.
if. y isCurzon current do. found =. found , current end.
current =. >: current
end.
y ; (5 10 $ found) ; {: found
}}
('Base';'First 50';'1000th') , generateCurzons"0 +:>:i.5
- Output:
+----+-------------------------------------------------+------+ |Base|First 50 |1000th| +----+-------------------------------------------------+------+ |2 | 1 2 5 6 9 14 18 21 26 29 |8646 | | | 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 | | +----+-------------------------------------------------+------+ |4 | 1 3 7 9 13 15 25 27 37 39 |9375 | | | 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 | | +----+-------------------------------------------------+------+ |6 | 1 6 30 58 70 73 90 101 105 121 |20717 | | |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 | | +----+-------------------------------------------------+------+ |8 | 1 14 35 44 72 74 77 129 131 137 |22176 | | |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 | | +----+-------------------------------------------------+------+ |10 | 1 9 10 25 106 145 190 193 238 253|46845 | | | 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| | +----+-------------------------------------------------+------+
Java
public final class CurzonNumbers {
public static void main(String[] aArgs) {
for ( int k = 2; k <= 10; k += 2 ) {
System.out.println("Generalised Curzon numbers with base " + k + ":");
int n = 1;
int count = 0;
while ( count < 50 ) {
if ( isGeneralisedCurzonNumber(k, n) ) {
System.out.print(String.format("%4d%s", n, ( ++count % 10 == 0 ? "\n" : " " )));
}
n += 1;
}
while ( count < 1_000 ) {
if ( isGeneralisedCurzonNumber(k, n) ) {
count += 1;
}
n += 1;
}
System.out.println("1,000th Generalised Curzon number with base " + k + ": " + ( n - 1 ));
System.out.println();
}
}
private static boolean isGeneralisedCurzonNumber(int aK, int aN) {
final long r = aK * aN;
return modulusPower(aK, aN, r + 1) == r;
}
private static long modulusPower(long aBase, long aExponent, long aModulus) {
if ( aModulus == 1 ) {
return 0;
}
aBase %= aModulus;
long result = 1;
while ( aExponent > 0 ) {
if ( ( aExponent & 1 ) == 1 ) {
result = ( result * aBase ) % aModulus;
}
aBase = ( aBase * aBase ) % aModulus;
aExponent >>= 1;
}
return result;
}
}
- Output:
Generalised 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 1,000th Generalised Curzon number with base 2: 8646 Generalised 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 1,000th Generalised Curzon number with base 4: 9375 Generalised 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 1,000th Generalised Curzon number with base 6: 20717 Generalised 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 1,000th Generalised Curzon number with base 8: 22176 Generalised 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 1,000th Generalised Curzon number with base 10: 46845
jq
Adapted from Julia
Works with gojq, the Go implementation of jq
The following jq program requires gojq for integer-arithmetic accuracy.
Preliminaries
# To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;
# gojq does not currently define _nwise
def _nwise($n):
def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;
n;
def printRows($m): _nwise($m) | map(lpad(5)) | join("");
The task
def isCurzon($n; $k):
($k | power($n) + 1) % ($k * $n + 1) == 0;
# Emit a stream of Curzon numbers base $k
def curzons($k):
range(0; infinite) | select(isCurzon(.; $k));
# Print the first 50 and the $n-th Curzon numbers
# for k in range(klow; khigh+1; 2)
def printcurzons(klow; khigh; $n):
range(klow; khigh+1; 2) as $k
| [limit($n; curzons($k))] as $curzons
| "Curzon numbers with k = \($k):",
($curzons[:50] | printRows(25) ),
" \($n)-th Curzon with k = \($k): \($curzons[$n - 1])",
"";
printcurzons(2; 10; 1000)
- Output:
Curzon numbers with k = 2: 0 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 1000-th Curzon with k = 2: 8645 Curzon numbers with k = 4: 0 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 1000-th Curzon with k = 4: 9373 Curzon numbers with k = 6: 0 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 1000-th Curzon with k = 6: 20681 Curzon numbers with k = 8: 0 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 1000-th Curzon with k = 8: 22122 Curzon numbers with k = 10: 0 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 1000-th Curzon with k = 10: 46837
Julia
isCurzon(n, k) = (BigInt(k)^n + 1) % (k * n + 1) == 0
function printcurzons(klow, khigh)
for k in filter(iseven, klow:khigh)
n, curzons = 0, Int[]
while length(curzons) < 1000
isCurzon(n, k) && push!(curzons, n)
n += 1
end
println("Curzon numbers with k = $k:")
foreach(p -> print(lpad(p[2], 5), p[1] % 25 == 0 ? "\n" : ""), enumerate(curzons[1:50]))
println(" Thousandth Curzon with k = $k: ", curzons[1000])
end
end
printcurzons(2, 10)
- Output:
Curzon numbers with k = 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 Thousandth Curzon with k = 2: 8646 Curzon numbers with k = 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 Thousandth Curzon with k = 4: 9375 Curzon numbers with k = 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 Thousandth Curzon with k = 6: 20717 Curzon numbers with k = 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 Thousandth Curzon with k = 8: 22176 Curzon numbers with k = 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 Thousandth Curzon with k = 10: 46845
Lambdatalk
Using Javascript's BigInt.
{def is_curzon
{lambda {:n :k}
{= {BI.% {BI.+ {BI.** :k :n} 1}
{BI.+ {BI.* :k :n} 1} } 0}}}
-> is_curzon
{def curzon
{lambda {:length :base}
{S.replace \s by space in
{S.brmap {{lambda {:length :base :count :i}
{if {< {A.get 0 :count} :length}
then {if {is_curzon :i :base}
then {{lambda {:a :i} :i}
{A.set! 0 {+ {A.get 0 :count} 1} :count} :i}
else}
else _break_}
} :length :base {A.new 0}}
1 100000 1 }}}}
-> curzon
{S.map {lambda {:i}
{div {b First 50 Curzon numbers using a base of :i:}
{div {curzon 50 :i}}}}
{S.serie 2 10 2}}
->
First 50 Curzon numbers using a base of 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
First 50 Curzon numbers using a base of 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
First 50 Curzon numbers using a base of 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
First 50 Curzon numbers using a base of 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
First 50 Curzon numbers using a base of 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
{S.last {curzon 1000 6}} -> 20717 in 272193ms = 4.53655 minutes
Maxima
/* Predicate function that checks wether a positive integer is generalized k-Curzon number or not */
g_curzonp(n,k):=if mod((k^n)+1,k*n+1)=0 then true$
/* Function that returns a list of the first len generalized k-Curzon numbers */
g_curzon_count(len,k):=block(
[i:1,count:0,result:[]],
while count<len do (if g_curzonp(i,k) then (result:endcons(i,result),count:count+1),i:i+1),
result)$
/* Test cases */
g_curzon_count(50,2);
g_curzon_count(50,4);
g_curzon_count(50,6);
g_curzon_count(50,8);
g_curzon_count(50,10);
- Output:
[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] [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] [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] [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] [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]
Nim
Nim standard library doesn’t provide a modular power, so we have to define our own function.
import std/strformat
func pow(a, n: Natural; m: Positive): Natural =
var a = a mod m
var n = n
if a > 0:
result = 1
while n > 0:
if (n and 1) != 0:
result = (result * a) mod m
n = n shr 1
a = (a * a) mod m
iterator curzonNumbers(k: Positive): Natural =
assert (k and 1) == 0, "base must be even."
var n = 1
while true:
let m = k * n + 1
if pow(k, n, m) + 1 == m:
yield n
inc n
### Task ###
for k in countup(2, 10, 2):
echo &"Curzon numbers for k = {k}:"
var count = 0
for n in curzonNumbers(k):
inc count
stdout.write &"{n:>4}"
stdout.write if count mod 10 == 0: '\n' else: ' '
if count == 50: break
echo()
### Stretch task ###
for k in countup(2, 10, 2):
var count = 0
for n in curzonNumbers(k):
inc count
if count == 1000:
echo &"1000th Curzon number for k = {k:>2}: {n:>5}"
break
- Output:
Curzon numbers for k = 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 Curzon numbers for k = 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 Curzon numbers for k = 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 Curzon numbers for k = 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 Curzon numbers for k = 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 Curzon number for k = 2: 8646 1000th Curzon number for k = 4: 9375 1000th Curzon number for k = 6: 20717 1000th Curzon number for k = 8: 22176 1000th Curzon number for k = 10: 46845
OCaml
let modpow m =
let rec loop p b e =
if e land 1 = 0
then if e = 0 then p else loop p (b * b mod m) (e lsr 1)
else loop (p * b mod m) (b * b mod m) (e lsr 1)
in loop 1
let is_curzon k n =
let r = k * n in r = modpow (succ r) k n
let () =
List.iter (fun x ->
Seq.(ints 0 |> filter (is_curzon x) |> take 50 |> map string_of_int)
|> List.of_seq |> String.concat " " |> Printf.printf "base %u:\n%s\n" x)
[2; 4; 6; 8; 10]
let () =
List.iter (fun x ->
Seq.(ints 0 |> filter (is_curzon x) |> drop 999 |> take 1
|> iter (Printf.printf "base %u (1000th): %u\n" x)))
[2; 4; 6; 8; 10]
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 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 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 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 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 base 2 (1000th): 8646 base 4 (1000th): 9375 base 6 (1000th): 20717 base 8 (1000th): 22176 base 10 (1000th): 46845
Odin
package curzon_numbers
/* imports */
import "core:c/libc"
import "core:fmt"
/* main block */
main :: proc() {
for k: int = 2; k <= 10; k += 2 {
fmt.println("\nCurzon numbers with base ", k)
count := 0
n: int = 1
for ; count < 50; n += 1 {
if is_curzon(n, k) {
count += 1
libc.printf("%*d ", 4, n)
if (count) % 10 == 0 {
fmt.printf("\n")
}
}
}
for {
if is_curzon(n, k) {
count += 1}
if count == 1000 {
break}
n += 1
}
libc.printf("1000th Curzon number with base %d: %d \n", k, n)
}
}
/* definitions */
modpow :: proc(base, exp, mod: int) -> int {
if mod == 1 {
return 0}
result: int = 1
base := base
exp := exp
base %= mod
for ; exp > 0; exp >>= 1 {
if ((exp & 1) == 1) {
result = (result * base) % mod}
base = (base * base) % mod
}
return result
}
is_curzon :: proc(n: int, k: int) -> bool {
r := k * n //const?
return modpow(k, n, r + 1) == r
}
- Output:
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 Curzon number with base 2: 8646 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 Curzon number with base 4: 9375 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 Curzon number with base 6: 20717 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 Curzon number with base 8: 22176 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 Curzon number with base 10: 46845
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.
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.
- Output:
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
Mathematica/Wolfram Language
ClearAll[CurzonNumberQ]
CurzonNumberQ[b_Integer][n_Integer]:=PowerMod[b,n,b n+1]==b n
val=Select[Range[100000],CurzonNumberQ[2]];
Take[val,50]
val[[1000]]
val=Select[Range[100000],CurzonNumberQ[4]];
Take[val,50]
val[[1000]]
val=Select[Range[100000],CurzonNumberQ[6]];
Take[val,50]
val[[1000]]
val=Select[Range[100000],CurzonNumberQ[8]];
Take[val,50]
val[[1000]]
val=Select[Range[100000],CurzonNumberQ[10]];
Take[val,50]
val[[1000]]
- Output:
{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} 8646 {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} 9375 {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} 20717 {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} 22176 {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} 46845
PARI/GP
/* Define the CurzonNumberQ function for base b */
powermod(a,k,n)=lift(Mod(a,n)^k)
CurzonNumberQ(b, n) = (powermod(b,n,b*n+1)== b*n);
/* Define a function to find Curzon numbers within a range for base b */
FindCurzonNumbers(b, maxrange) = {
local(val, res, i);
val = vector(maxrange);
res = [];
for(i = 1, maxrange,
if(CurzonNumberQ(b, i), res = concat(res, i));
);
return(Vec(res));
}
/* Select and display the first 50 Curzon numbers and the 1000th for base 2 */
val = FindCurzonNumbers(2, 100000);
print(vector(50, i, val[i])); /* First 50 */
print(val[1000]); /* 1000th Curzon number */
/* Select and display for base 4 */
val = FindCurzonNumbers(4, 100000);
print(vector(50, i, val[i])); /* First 50 */
print(val[1000]); /* 1000th Curzon number */
/* Select and display for base 6 */
val = FindCurzonNumbers(6, 100000);
print(vector(50, i, val[i])); /* First 50 */
print(val[1000]); /* 1000th Curzon number */
/* Select and display for base 8 */
val = FindCurzonNumbers(8, 100000);
print(vector(50, i, val[i])); /* First 50 */
print(val[1000]); /* 1000th Curzon number */
/* Select and display for base 10 */
val = FindCurzonNumbers(10, 100000);
print(vector(50, i, val[i])); /* First 50 */
print(val[1000]); /* 1000th Curzon number */
- Output:
[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] 8646 [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] 9375 [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] 20717 [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] 22176 [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] 46845
Perl
use strict;
use warnings;
use ntheory 'powmod';
sub curzon {
my($base,$cnt) = @_;
my($n,@C) = 0;
while (++$n) {
my $r = $base * $n;
push @C, $n if powmod($base, $n, $r + 1) == $r;
return @C if $cnt == @C;
}
}
my $upto = 50;
for my $k (<2 4 6 8 10>) {
my @C = curzon $k, 1000;
print "First $upto Curzon numbers using a base of $k:\n" .
(sprintf "@{['%5d' x $upto]}", @C[0..$upto-1]) =~ s/.{100}/$&\n/gr;
printf "%50s\n\n", "Thousandth: $C[-1]"
}
- Output:
First 50 Curzon numbers using a base of 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 Thousandth: 8646 First 50 Curzon numbers using a base of 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 Thousandth: 9375 First 50 Curzon numbers using a base of 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 Thousandth: 20717 First 50 Curzon numbers using a base of 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 Thousandth: 22176 First 50 Curzon numbers using a base of 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 Thousandth: 46845
Phix
with javascript_semantics include mpfr.e mpz {pow,z} = mpz_inits(2) for base=2 to 10 by 2 do printf(1,"The first 50 Curzon numbers using a base of %d:\n",base) integer count = 0, n = 1 mpz_set_si(pow,base) while true do mpz_add_ui(z,pow,1) integer d = base*n + 1 if mpz_divisible_ui_p(z,d) then count = count + 1 if count<=50 then printf(1,"%5d%s",{n,iff(remainder(count,25)=0?"\n":"")}) elsif count=1000 then printf(1,"One thousandth: %d\n\n",n) exit end if end if n += 1 mpz_mul_si(pow,pow,base) end while end for
- Output:
The first 50 Curzon numbers using a base of 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 One thousandth: 8646 The first 50 Curzon numbers using a base of 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 One thousandth: 9375 The first 50 Curzon numbers using a base of 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 One thousandth: 20717 The first 50 Curzon numbers using a base of 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 One thousandth: 22176 The first 50 Curzon numbers using a base of 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 One thousandth: 46845
Python
def is_Curzon(n, k):
r = k * n
return pow(k, n, r + 1) == r
for k in [2, 4, 6, 8, 10]:
n, curzons = 1, []
while len(curzons) < 1000:
if is_Curzon(n, k):
curzons.append(n)
n += 1
print(f'Curzon numbers with k = {k}:')
for i, c in enumerate(curzons[:50]):
print(f'{c: 5,}', end='\n' if (i + 1) % 25 == 0 else '')
print(f' Thousandth Curzon with k = {k}: {curzons[999]}.\n')
- Output:
Curzon numbers with k = 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 Thousandth Curzon with k = 2: 8646. Curzon numbers with k = 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 Thousandth Curzon with k = 4: 9375. Curzon numbers with k = 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 Thousandth Curzon with k = 6: 20717. Curzon numbers with k = 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 Thousandth Curzon with k = 8: 22176. Curzon numbers with k = 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 1,033 1,077 1,125 1,126 1,141 1,149 1,230 1,405 1,422 1,441 1,485 1,509 1,510 1,513 1,606 1,614 1,630 1,665 1,681 1,690 1,702 1,785 1,837 Thousandth Curzon with k = 10: 46845.
Quackery
[ number$
space 4 of swap join
-5 split nip echo$ ] is rjust ( n --> )
[ 5 times
[ 10 times
[ behead rjust ]
cr ]
drop ] is display ( [ --> )
[ temp take
over join
temp put ] is dax ( [ --> )
[ 2dup ** 1+
unrot * 1+ mod 0 = ] is curzon ( n n --> b )
5 times
[ i^ 1+ 2 *
say "Curzon numbers base "
dup echo cr
1
[] temp put
[ 2dup curzon if dax
temp share
size 1000 < while
1+ again ]
2drop
temp take
50 split swap display
say " ... "
-1 peek echo cr cr ]
- Output:
Curzon numbers 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 ... 8646 Curzon numbers 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 ... 9375 Curzon numbers 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 ... 20717 Curzon numbers 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 ... 22176 Curzon numbers 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 ... 46845
Raku
sub curzon ($base) { lazy (1..∞).hyper.map: { $_ if (exp($_, $base) + 1) %% ($base × $_ + 1) } };
for <2 4 6 8 10> {
my $curzon = .&curzon;
say "\nFirst 50 Curzon numbers using a base of $_:\n" ~
$curzon[^50].batch(10)».fmt("%4s").join("\n") ~
"\nOne thousandth: " ~ $curzon[999]
}
- Output:
First 50 Curzon numbers using a base of 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 One thousandth: 8646 First 50 Curzon numbers using a base of 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 One thousandth: 9375 First 50 Curzon numbers using a base of 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 One thousandth: 20717 First 50 Curzon numbers using a base of 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 One thousandth: 22176 First 50 Curzon numbers using a base of 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 One thousandth: 46845
RPL
Code | Comments |
---|---|
≪ → x n m ≪ IF OVER THEN 1 1 n START x * m MOD NEXT ELSE 1 END ≫ ≫ 'XnMOD' STO ≪ → k ≪ {} 1 WHILE OVER SIZE 50 < REPEAT k OVER * 1 + DUP2 k ROT ROT XnMOD 1 + SWAP MOD IF NOT THEN SWAP OVER + SWAP END 1 + END DROP ≫ ≫ 'QRZ50' STO |
( x n m -- (x^n mod m) ) If n<>0... then x^n mod m = (((x mod m) * x mod m) ... * x mod m) else x^0 mod m = 1 ( k -- { 50 Curzon numbers } ) Initialize Get k*n + 1 Get k^n+1 mod k*n+1 If zero then add it to sequence Increment n |
The following line of code delivers what is required:
2 QRZ50 10 QRZ50
- Output:
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 } 1: { 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 }
Ruby
def curzons(k)
Enumerator.new do |y|
(1..).each do |n|
r = k * n
y << n if k.pow(n, r + 1) == r
end
end
end
[2,4,6,8,10].each do |base|
puts "Curzon numbers with k = #{base}:"
puts curzons(base).take(50).join(", ")
puts "Thousandth Curzon with k = #{base}: #{curzons(base).find.each.with_index(1){|_,i| i == 1000} }",""
end
- Output:
Curzon numbers with k = 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 Thousandth Curzon with k = 2: 8646.
Curzon numbers with k = 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 Thousandth Curzon with k = 4: 9375.
Curzon numbers with k = 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 Thousandth Curzon with k = 6: 20717.
Curzon numbers with k = 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 Thousandth Curzon with k = 8: 22176.
Curzon numbers with k = 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 Thousandth Curzon with k = 10: 46845.
Rust
fn modpow(mut base: usize, mut exp: usize, n: usize) -> usize {
if n == 1 {
return 0;
}
let mut result = 1;
base %= n;
while exp > 0 {
if (exp & 1) == 1 {
result = (result * base) % n;
}
base = (base * base) % n;
exp >>= 1;
}
result
}
fn is_curzon(n: usize, k: usize) -> bool {
let m = k * n + 1;
modpow(k, n, m) + 1 == m
}
fn main() {
for k in (2..=10).step_by(2) {
println!("Curzon numbers with base {k}:");
let mut count = 0;
let mut n = 1;
while count < 50 {
if is_curzon(n, k) {
count += 1;
print!("{:4}{}", n, if count % 10 == 0 { "\n" } else { " " });
}
n += 1;
}
loop {
if is_curzon(n, k) {
count += 1;
if count == 1000 {
break;
}
}
n += 1;
}
println!("1000th Curzon number with base {k}: {n}\n");
}
}
- Output:
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 Curzon number with base 2: 8646 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 Curzon number with base 4: 9375 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 Curzon number with base 6: 20717 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 Curzon number with base 8: 22176 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 Curzon number with base 10: 46845
Sidef
func is_curzon(n, k) {
powmod(k, n, k*n + 1).is_congruent(-1, k*n + 1) && (n > 0)
}
for k in (2 .. 10 `by` 2) {
say "\nFirst 50 Curzon numbers using a base of #{k}:"
say 50.by {|n| is_curzon(n, k) }.join(' ')
say ("1000th term: ", 1000.th {|n| is_curzon(n,k) })
}
- Output:
First 50 Curzon numbers using a base of 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 term: 8646 First 50 Curzon numbers using a base of 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 term: 9375 First 50 Curzon numbers using a base of 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 term: 20717 First 50 Curzon numbers using a base of 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 term: 22176 First 50 Curzon numbers using a base of 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 term: 46845
V (Vlang)
import math.big
fn main() {
zero := big.zero_int
one := big.one_int
for k := i64(2); k <= 10; k += 2 {
bk := big.integer_from_i64(k)
println("The first 50 Curzon numbers using a base of $k:")
mut count := 0
mut n := i64(1)
mut pow := big.integer_from_i64(k)
mut curzon50 := []i64{}
for {
z := pow + one
d := k*n + 1
bd := big.integer_from_i64(d)
if z%bd == zero {
if count < 50 {
curzon50 << n
}
count++
if count == 50 {
for i in 0..curzon50.len {
print("${curzon50[i]:4} ")
if (i+1)%10 == 0 {
println('')
}
}
print("\nOne thousandth: ")
}
if count == 1000 {
println(n)
break
}
}
n++
pow *= bk
}
println('')
}
}
- Output:
The first 50 Curzon numbers using a base of 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 One thousandth: 8646 The first 50 Curzon numbers using a base of 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 One thousandth: 9375 The first 50 Curzon numbers using a base of 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 One thousandth: 20717 The first 50 Curzon numbers using a base of 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 One thousandth: 22176 The first 50 Curzon numbers using a base of 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 One thousandth: 46845
Wren
Version 1 (Embedded using GMP)
/* Curzon_numbers.wren */
import "./gmp" for Mpz
import "./fmt" for Fmt
for (k in [2, 4, 6, 8, 10]) {
System.print("The first 50 Curzon numbers using a base of %(k):")
var count = 0
var n = 1
var pow = Mpz.from(k)
var curzon50 = []
while (true) {
var z = pow + Mpz.one
var d = k*n + 1
if (z.isDivisibleUi(d)) {
if (count < 50) curzon50.add(n)
count = count + 1
if (count == 50) {
Fmt.tprint("$4d", curzon50, 10)
System.write("\nOne thousandth: ")
}
if (count == 1000) {
Fmt.print("$,d", n)
break
}
}
n = n + 1
pow.mul(k)
}
System.print()
}
- Output:
The first 50 Curzon numbers using a base of 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 One thousandth: 8,646 The first 50 Curzon numbers using a base of 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 One thousandth: 9,375 The first 50 Curzon numbers using a base of 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 One thousandth: 20,717 The first 50 Curzon numbers using a base of 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 One thousandth: 22,176 The first 50 Curzon numbers using a base of 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 One thousandth: 46,845
Version 2 (Wren-cli)
Alternatively, using Int.modPow rather than GMP so it will run on Wren-cli, albeit about 6 times more slowly.
import "./math" for Int
import "./fmt" for Fmt
var isCurzon = Fn.new { |n, k|
var r = k * n
return Int.modPow(k, n, r+1) == r
}
var k = 2
while (k <= 10) {
System.print("Curzon numbers with base %(k):")
var n = 1
var count = 0
while (count < 50) {
if (isCurzon.call(n, k)) {
Fmt.write("$4d ", n)
count = count + 1
if (count % 10 == 0) System.print()
}
n = n + 1
}
while (true) {
if (isCurzon.call(n, k)) count = count + 1
if (count == 1000) break
n = n + 1
}
Fmt.print("1,000th Curzon number with base $d: $,d\n", k, n)
k = k + 2
}
- Output:
As Version 1.
XPL0
func ModPow(Base, Exp, Mod);
int Base, Exp, Mod, Result;
[if Mod = 1 then return 0;
Result:= 1;
Base:= rem(Base/Mod);
while Exp > 0 do
[if (Exp&1) = 1 then Result:= rem((Result*Base)/Mod);
Base:= rem((Base*Base) / Mod);
Exp:= Exp >> 1;
];
return Result;
];
func IsCurzon(N, K);
int N, K, R;
[R:= K * N;
return ModPow(K, N, R+1) = R;
];
int K, N, Count;
[K:= 2;
Format(5, 0);
while K <= 10 do
[Text(0, "Curzon numbers with base "); IntOut(0, K); CrLf(0);
N:= 1; Count:= 0;
while Count < 50 do
[if IsCurzon(N, K) then
[RlOut(0, float(N));
Count:= Count+1;
if rem(Count/10) = 0 then CrLf(0);
];
N:= N+1;
];
K:= K+2;
];
]
- Output:
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 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 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 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 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