Rosetta Code

Deceptive numbers: Difference between revisions

Page Discussion

Deceptive numbers (view source)

Revision as of 19:02, 1 May 2024

10,606 bytes added ,  16 days ago
m
→‎{{header|langur}}
(→‎C: do the Fermat primality test first; generate 500 numbers in 1.6 s)
 
(21 intermediate revisions by 9 users not shown)
Line 64:
<pre>
91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601
</pre>
 
=={{header|ALGOL W}}==
Based on the second Wren sample - finds the numbers without needing large integers - see the Talk page.
<syntaxhighlight lang="algolw">
begin % find deceptive numbers - repunits R(n) evenly divisible by composite %
% numbers and n+1; see the task talk page based on the second Wren sample %
 
% returns true if n is an odd prime, false otherwise, uses trial division %
logical procedure isOddPrime ( integer value n ) ;
begin
logical prime;
integer f, f2, toNext;
prime := true;
f := 3;
f2 := 9;
toNext := 16; % note: ( 2n + 1 )^2 - ( 2n - 1 )^2 = 8n %
while f2 <= n and prime do begin
prime := n rem f not = 0;
f := f + 2;
f2 := toNext;
toNext := toNext + 8
end while_f2_le_n_and_prime ;
prime
end isOddPrime ;
 
begin % -- task %
integer n, count;
count := 0;
n := 47;
while begin n := n + 2;
count < 25
end
do begin
if n rem 3 not = 0 and n rem 5 not = 0 and not isOddPrime( n ) then begin
integer mp;
mp := 10;
for p := 2 until n - 1 do mp := ( mp * 10 ) rem n;
if mp = 1 then begin
count := count + 1;
writeon( i_w := 5, s_w := 0, " ", n );
if count rem 10 = 0 then write()
end if_mp_eq_1
end if_have_a_candidate
end while_count_lt_50
end task
 
end.
</syntaxhighlight>
{{out}}
<pre>
91 259 451 481 703 1729 2821 2981 3367 4141
4187 5461 6533 6541 6601 7471 7777 8149 8401 8911
10001 11111 12403 13981 14701
</pre>
 
Line 146 ⟶ 200:
3367
4141</pre>
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">function modpow(b, e, m, r) {
for (r = 1; e > 0; e = int(e / 2)) {
if (e % 2 == 1)
r = r * b % m
b = b * b % m
}
return r
}
 
function is_pseudo(n, i, p, r) {
if (modpow(10, n - 1, n) == 1) {
r = int(sqrt(n))
while ((p = primes[++i]) <= r)
if (n % p == 0)
return 1
primes[++l] = n
}
return 0
}
 
BEGIN {
primes[l = 1] = n = 7
split("4 2 4 2 4 6 2 6", wheel)
 
do if (is_pseudo(n += wheel[i = i % 8 + 1])) {
printf " %u", n
++c
} while (c != 50)
print
}</syntaxhighlight>
{{out}}
<pre> 91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001 11111 12403 13981 14701 14911 15211 15841 19201 21931 22321 24013 24661 27613 29341 34133 34441 35113 38503 41041 45527 46657 48433 50851 50881 52633 54913 57181 63139 63973</pre>
 
=={{header|bc}}==
<syntaxhighlight lang="bc">/* modular exponentiation */
define p(b, e, m) {
auto r
for (r = 1; e > 0; e /= 2) {
if (e % 2 == 1) r = r * b % m
b = b * b % m
}
return(r)
}
 
/* cache for the primes found */
p[0] = 7
 
define d(n) {
auto i, p, r;
if (p(10, n - 1, n) == 1) {
for (r = sqrt(n); (p = p[i]) <= r; ++i) if (n % p == 0) return(1)
p[++l] = n
}
return(0)
}
 
/* wheel to skip multiples of 2, 3, and 5 */
w[0] = 4
w[1] = 2
w[2] = 4
w[3] = 2
w[4] = 4
w[5] = 6
w[6] = 2
w[7] = 6
 
for (n = p[0]; c != 10; i = (i + 1) % 8) {
if (d(n += w[i]) == 1) {
n
c += 1
}
}</syntaxhighlight>
{{out}}
<pre>
91
259
451
481
703
1729
2821
2981
3367
4141
</pre>
 
=={{header|C}}==
<syntaxhighlight lang="c">#include <stdintinttypes.h>
#include <stdio.h>
 
Line 180 ⟶ 321:
for (c = 0; c != 500; ++n) {
if (is_deceptive(n)) {
printf(" %u" PRIu32, n);
++c;
}
Line 247 ⟶ 388:
#include <iostream>
 
uint64_t power_modulus(uint64_t base, uint64_t exponent, const uint64_t& modulus) {
if ( modulus == 1 ) {
return 0;
Line 255 ⟶ 396:
uint64_t result = 1;
while ( exponent > 0 ) {
if ( ( exponent & 1 ) == 1 ) {
result = ( result * base ) % modulus;
}
Line 264 ⟶ 405:
}
 
bool is_deceptive(const uint32_t& n) {
if ( n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && power_modulus(10, n - 1, n) == 1 ) {
for ( uint32_t divisor = 7; divisor < sqrt(n); divisor += 6 ) {
Line 298 ⟶ 439:
137149 138481 139231 145181 147001 148417 152551 158497 162401 164761
166499 170017 172081 179881 188191 188269 188461 188501 196651 201917
</pre>
 
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
func modpow b e m .
r = 1
while e > 0
if e mod 2 = 1
r = r * b mod m
.
b = b * b mod m
e = e div 2
.
return r
.
func is_deceptive n .
if n mod 2 = 1 and n mod 3 <> 0 and n mod 5 <> 0
if modpow 10 (n - 1) n = 1
x = 7
while x * x <= n
if n mod x = 0 or n mod (x + 4) = 0
return 1
.
x += 6
.
.
.
.
while cnt < 10
n += 1
if is_deceptive n = 1
write n & " "
cnt += 1
.
.
</syntaxhighlight>
{{out}}
<pre>
91 259 451 481 703 1729 2821 2981 3367 4141
</pre>
 
Line 344 ⟶ 525:
if Isprime(n)>1 and Divides(n,Rep(n-1)) then !!n; c:+; fi
od;</syntaxhighlight>
 
=={{header|FreeBASIC}}==
{{trans|XPLo}}
<syntaxhighlight lang="vbnet">Function ModPow(b As Uinteger, e As Uinteger, m As Uinteger) As Uinteger
Dim As Uinteger p = 1
While e <> 0
If (e And 1) Then p = (p*b) Mod m
b = (b*b) Mod m
e Shr= 1
Wend
Return p
End Function
 
Function isDeceptive(n As Uinteger) As Uinteger
Dim As Uinteger x
If (n And 1) <> 0 Andalso (n Mod 3) <> 0 Andalso (n Mod 5) <> 0 Then
x = 7
While x*x <= n
If (n Mod x) = 0 Orelse (n Mod (x+4)) = 0 Then Return (ModPow(10, n-1, n) = 1)
x += 6
Wend
End If
Return 0
End Function
 
Dim As Uinteger c = 0, i = 49
While c <> 41 ' limit for signed 32-bit integers
If isDeceptive(i) Then
Print Using "#######"; Csng(i);
c += 1
If (c Mod 10) = 0 Then Print
End If
i += 1
Wend
 
Sleep</syntaxhighlight>
{{out}}
<pre>Same as XPLo entry.</pre>
 
=={{header|Go}}==
Line 389 ⟶ 608:
 
=={{header|J}}==
<syntaxhighlight lang="j">Rwheel=:. (10x4 #.6 2 6 4 2 4 #&1)"02
deceptivefermat=:. {{1&p: < 0 = ]10 (y&|@^) R@<: y}}"0
 
2+I.deceptive 2+i.10000
91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001</syntaxhighlight>
 
For improved performance:
 
<syntaxhighlight lang="j">deceptives=: {{
r=.$k=.10x #.}.1#~j=.9
while. y>#r do.
if. 0<2|j do.
if. 0<5|j do.
if. 0=1 p:j do.
if. 0=0]j|k do.
r=. r, j
end.
end.
end.
end.
k=. 1 10x p.k
j=. j+1
end.
r
}}</syntaxhighlight>
 
_10 ]\ (#~ fermat) (#~ 0&p:) +/\ 49 , 15e4 $ wheel</syntaxhighlight>
{{out}}
<pre>
<syntaxhighlight lang="j"> deceptives 21
91 259 451 481 703 1729 2821 2981703 3367 4141 41871729 5461 6533 65412821 6601 7471 77772981 8149 8401 89113367 10001</syntaxhighlight> 4141
4187 5461 6533 6541 6601 7471 7777 8149 8401 8911
10001 11111 12403 13981 14701 14911 15211 15841 19201 21931
22321 24013 24661 27613 29341 34133 34441 35113 38503 41041
45527 46657 48433 50851 50881 52633 54913 57181 63139 63973
65311 66991 67861 68101 75361 79003 82513 83119 94139 95161
97273 97681 100001 101101 101491 102173 108691 113201 115627 115921
118301 118957 122221 126217 128713 130351 131821 134821 134863 137137
137149 138481 139231 145181 147001 148417 152551 158497 162401 164761
166499 170017 172081 179881 188191 188269 188461 188501 196651 201917
216001 216931 225589 226273 229633 231337 234421 237169 237817 245491
247753 248677 250717 251251 252601 253099 269011 269569 274231 281821
286903 287749 287809 294409 298033 301081 302177 304057 314821 334153
340561 341503 346801 351809 357641 364277 366337 372731 385003 390313
391141 399001 401401 410041 413339 420343 437251 451091 455971 458641
463241 463489 481601 488881 489997 491063 492101 497377 497503 497927
505363 507529 509971 511969 512461 520801 522349 530881 532171 552721
</pre>
 
=={{header|Java}}==
Line 547 ⟶ 761:
=={{header|langur}}==
{{trans|ALGOL 68}}
<syntaxhighlight lang="langur">val .isPrime = fn(.i) {
{{works with|langur|0.8.1}}
.i == 2 or .i > 2 and
<syntaxhighlight lang="langur">val .isPrime = f .i == 2 or .i > 2 and not any f(.x) .i div .x, pseries 2 .. .i ^/ 2
not any fn(.x) { .i div .x }, pseries 2 .. .i ^/ 2
}
 
var .nums = []
Line 554 ⟶ 770:
 
for .n = 9; len(.nums) < 10; .n += 2 {
.repunit = .repunit x* 100 + 11
if not .isPrime(.n) and .repunit div .n {
.nums = more .nums, .n
Line 607 ⟶ 823:
(91 259 451 481 703 1729 2821 2981 3367 4141)
ok
</pre>
 
=={{header|Lua}}==
Based on the second Wren sample, finds the numbers without needing large integers - see the talk page for more details.
<syntaxhighlight lang="lua">
do -- find deceptive numbers - repunits R(n) evenly divisible by composite numbers and n+1
-- see tha task talk page based on the second Wren sample
 
-- returns true if n is prime, false otherwise, uses trial division %
local function isPrime ( n )
if n < 3 then return n == 2
elseif n % 3 == 0 then return n == 3
elseif n % 2 == 0 then return false
else
local prime = true
local f, f2, toNext = 5, 25, 24
while f2 <= n and prime do
prime = n % f ~= 0
f = f + 2
f2 = toNext
toNext = toNext + 8
end
return prime
end
end
 
do -- task
local n, count = 47, 0
while count < 25 do
n = n + 2
if n % 3 ~= 0 and n % 5 ~= 0 and not isPrime( n ) then
local mp = 10
for p = 2, n - 1 do mp = ( mp * 10 ) % n end
if mp == 1 then
count = count + 1
io.write( string.format( " %5d", n ) )
if count % 10 == 0 then io.write( "\n" ) end
end
end
end
end
 
end
</syntaxhighlight>
{{out}}
<pre>
91 259 451 481 703 1729 2821 2981 3367 4141
4187 5461 6533 6541 6601 7471 7777 8149 8401 8911
10001 11111 12403 13981 14701
</pre>
 
Line 1,019 ⟶ 1,284:
 
=={{header|Python}}==
;By using a generic test<nowiki>:</nowiki>
<syntaxhighlight lang="python">from itertools import count, islice
from math import isqrt
Line 1,028 ⟶ 1,294:
return False
 
print(*islice(filter(is_deceptive, count(49)), 100))</syntaxhighlight>
;Optimized variant to efficiently generate a sequence<nowiki>:</nowiki>
This uses a wheel to skip the multiples of 2, 3, and 5. The found primes are cached to speedup the full primality test.
<syntaxhighlight lang="python">from itertools import accumulate, cycle, islice
from math import isqrt
 
primes = []
wheel = 4, 2, 4, 2, 4, 6, 2, 6
 
def is_pseudo(n):
if pow(10, n - 1, n) == 1:
s = isqrt(n)
for p in primes:
if p > s: break
if n % p == 0: return True
primes.append(n)
return False
 
print(*islice(filter(is_pseudo, accumulate(cycle(wheel), initial=7)), 100))</syntaxhighlight>
{{out}}
<pre>91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001 11111 12403 13981 14701 14911 15211 15841 19201 21931 22321 24013 24661 27613 29341 34133 34441 35113 38503 41041 45527 46657 48433 50851 50881 52633 54913 57181 63139 63973 65311 66991 67861 68101 75361 79003 82513 83119 94139 95161 97273 97681 100001 101101 101491 102173 108691 113201 115627 115921 118301 118957 122221 126217 128713 130351 131821 134821 134863 137137 137149 138481 139231 145181 147001 148417 152551 158497 162401 164761 166499 170017 172081 179881 188191 188269 188461 188501 196651 201917</pre>
Line 1,053 ⟶ 1,337:
{{out}}
<pre>91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001 11111 12403 13981 14701</pre>
 
=={{header|RPL}}==
Based on the hints given on the Talk page.
{{works with|HP|49}}
« { } 49
'''WHILE''' OVER SIZE 10 < '''REPEAT'''
'''IF''' DUP 3 MOD OVER 5 MOD AND '''THEN'''
'''IF''' DUP ISPRIME? NOT '''THEN'''
DUP MODSTO 10 OVER 1 - POWMOD
'''IF''' 1 == '''THEN''' SWAP OVER + SWAP '''END'''
'''END END'''
2 +
'''END''' DROP
» '<span style="color:blue">TASK</span>' STO
Runs in 4 minutes on a HP-50g.
 
'''With a wheel:'''
« { 4 6 2 6 4 2 4 2 } DUP SIZE → wheel wsize
« { } 49
'''WHILE''' OVER SIZE 10 < '''REPEAT'''
1 wsize '''FOR''' j
'''IF''' DUP ISPRIME? NOT '''THEN'''
DUP MODSTO 10 OVER 1 - POWMOD
'''IF''' 1 == '''THEN''' SWAP OVER + SWAP '''END'''
'''END'''
wheel j GET +
'''NEXT'''
'''END''' DROP
» » '<span style="color:blue">TASK</span>' STO
Runs in 1:26 minutes on a HP-50g.
{{out}}
<pre>
1: { 91 259 451 481 703 1729 2821 2981 3367 4141 }
</pre>
 
=={{header|Ruby}}==
Line 1,155 ⟶ 1,473:
<pre>
91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001 11111 12403 13981 14701 14911 15211 15841 19201 21931 22321 24013 24661 27613 29341 34133 34441 35113 38503 41041 45527 46657 48433 50851 50881 52633 54913 57181 63139 63973 65311 66991 67861 68101 75361 79003 82513 83119 94139 95161 97273 97681 100001 101101 101491 102173 108691 113201 115627 115921 118301 118957 122221 126217 128713 130351 131821 134821 134863 137137 137149 138481 139231 145181 147001 148417 152551 158497 162401 164761 166499 170017 172081 179881 188191 188269 188461 188501 196651 201917
</pre>
 
=={{header|UNIX Shell}}==
Works with [[POSIX]]-compatible shells.
<syntaxhighlight lang="sh">is () {
return "$((!($1)))"
}
 
fermat_test () {
set -- 1 "$1" "$(($2 - 1))" "$2"
while is "$3 > 0"
do
set -- "$(($1 * (-($3 & 1) & ($2 ^ 1) ^ 1) % $4))" "$(($2 * $2 % $4))" "$(($3 >> 1))" "$4"
done
return "$(($1 != 1))"
}
 
set -- 7
c=0 n=$1
while :
do
for w in 4 2 4 2 4 6 2 6
do
fermat_test 10 "$((n += w))" && for p
do
is 'p * p > n' && {
set -- "$@" "$n"
break
}
is 'n % p == 0' && {
echo "$n"
is '(c += 1) == 10' && exit
break
}
done
done
done</syntaxhighlight>
{{out}}
<pre>
91
259
451
481
703
1729
2821
2981
3367
4141
</pre>
 
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="go">import math.big
import math.big
 
fn is_prime(n int) bool {
if n < 2 {return false}
else if n % 2 == 0 {return falsen == 2}
} else if n %2 3 == 0 {return n == 3}
else {
return n == 2
} else if n%3 == 0 {
return n == 3
} else {
mut d := 5
for d * d <= n {
if n % d == 0 {return false}
return false
}
d += 2
if n % d == 0 {return false}
return false
}
d += 4
}
Line 1,195 ⟶ 1,556:
mut deceptive := []i64{}
for count < limit {
if !is_prime(int(n)) && n % 3 != 0 && n % 5 != 0 {
bn := big.integer_from_i64(n)
t = repunit % bn
Line 1,224 ⟶ 1,585:
 
The first 62 deceptive numbers (up to 97681 though not shown in full) are found in 0.179 seconds.
<syntaxhighlight lang="ecmascriptwren">/* deceptive_numbersDeceptive_numbers.wren */
 
import "./gmp" for Mpz
Line 1,252 ⟶ 1,613:
[91, 259, 451, 481, 703, 1729, 2821, 2981, 3367, 4141, 4187, 5461, 6533, 6541, 6601, 7471, 7777, 8149, 8401, 8911, 10001, 11111, 12403, 13981, 14701]
</pre>
 
As discussed in the talk page, it is also possible to do this task without using big integers and the following version runs under Wren-cli albeit somewhat slower at 0.103 seconds for the first 25 deceptive numbers and 0.978 seconds for the first 62. The output is the same as the GMP version.
<syntaxhighlight lang="wren">import "./math" for Int
 
var count = 0
var limit = 25 // or 62
var n = 49
var deceptive = []
while (count < limit) {
if (!Int.isPrime(n) && n % 3 != 0 && n % 5 != 0 && Int.modPow(10, n-1, n) == 1) {
deceptive.add(n)
count = count + 1
}
n = n + 2
}
System.print("The first %(limit) deceptive numbers are:")
System.print(deceptive)</syntaxhighlight>
 
=={{header|XPL0}}==
Langurmonkey
885

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/355404...364132"