Deceptive numbers: Difference between revisions
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 43: | Line 43: | ||
As with the Phix, Wren and other samples we only consider odd n. |
As with the Phix, Wren and other samples we only consider odd n. |
||
{{libheader|ALGOL 68-primes}} |
{{libheader|ALGOL 68-primes}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find repunits (all digits are 1 ) such that R(n-1) is divisible by n and n is not prime # |
||
# R(n) is the nth repunit, so has n 1s # |
# R(n) is the nth repunit, so has n 1s # |
||
PR precision 8000 PR # set precision of LONG LONG INT, enough for up to R(8000) # |
PR precision 8000 PR # set precision of LONG LONG INT, enough for up to R(8000) # |
||
Line 60: | Line 60: | ||
FI |
FI |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 68: | Line 68: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">deceptive?: function [n][ |
||
and? -> not? prime? n |
and? -> not? prime? n |
||
-> zero? (to :integer repeat "1" n-1) % n |
-> zero? (to :integer repeat "1" n-1) % n |
||
Line 82: | Line 82: | ||
] |
] |
||
i: i + 2 |
i: i + 2 |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 99: | Line 99: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
< |
<syntaxhighlight lang="cpp">#include <gmpxx.h> |
||
#include <iomanip> |
#include <iomanip> |
||
Line 131: | Line 131: | ||
repunit += 11; |
repunit += 11; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 150: | Line 150: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Deceptive numbers. Nigel Galloway: February 13th., 2022 |
// Deceptive numbers. Nigel Galloway: February 13th., 2022 |
||
Seq.unfold(fun n->Some(n|>Seq.filter(isPrime>>not)|>Seq.filter(fun n->(10I**(n-1)-1I)%(bigint n)=0I),n|>Seq.map((+)30)))(seq{1;7;11;13;17;19;23;29})|>Seq.concat|>Seq.skip 1 |
Seq.unfold(fun n->Some(n|>Seq.filter(isPrime>>not)|>Seq.filter(fun n->(10I**(n-1)-1I)%(bigint n)=0I),n|>Seq.map((+)30)))(seq{1;7;11;13;17;19;23;29})|>Seq.concat|>Seq.skip 1 |
||
|>Seq.chunkBySize 10|>Seq.take 7|>Seq.iter(fun n->n|>Array.iter(printf "%7d "); printfn "") |
|>Seq.chunkBySize 10|>Seq.take 7|>Seq.iter(fun n->n|>Array.iter(printf "%7d "); printfn "") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 167: | Line 167: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2021-06-02}} |
{{works with|Factor|0.99 2021-06-02}} |
||
< |
<syntaxhighlight lang="factor">USING: io kernel lists lists.lazy math math.functions |
||
math.primes prettyprint ; |
math.primes prettyprint ; |
||
Line 177: | Line 177: | ||
composite [ [ 1 - repunit ] keep divisor? ] lfilter ; |
composite [ [ 1 - repunit ] keep divisor? ] lfilter ; |
||
10 deceptive ltake [ pprint bl ] leach nl</ |
10 deceptive ltake [ pprint bl ] leach nl</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 184: | Line 184: | ||
=={{header|Fermat}}== |
=={{header|Fermat}}== |
||
< |
<syntaxhighlight lang="fermat">Func Rep(n)=Sigma<m=0,n-1>[10^m].; |
||
c:=0; |
c:=0; |
||
n:=3; |
n:=3; |
||
Line 190: | Line 190: | ||
n:=n+1; |
n:=n+1; |
||
if Isprime(n)>1 and Divides(n,Rep(n-1)) then !!n; c:+; fi |
if Isprime(n)>1 and Divides(n,Rep(n-1)) then !!n; c:+; fi |
||
od;</ |
od;</syntaxhighlight> |
||
Line 196: | Line 196: | ||
{{trans|Wren}} |
{{trans|Wren}} |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 228: | Line 228: | ||
fmt.Println("The first", limit, "deceptive numbers are:") |
fmt.Println("The first", limit, "deceptive numbers are:") |
||
fmt.Println(deceptive) |
fmt.Println(deceptive) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 238: | Line 238: | ||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j">R=: (10x #. #&1)"0 |
||
deceptive=: 1&p: < 0 = ] | R@<: |
deceptive=: 1&p: < 0 = ] | R@<: |
||
2+I.deceptive 2+i.10000 |
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</ |
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: |
For improved performance: |
||
< |
<syntaxhighlight lang="j">deceptives=: {{ |
||
r=.$k=.10x #.}.1#~j=.9 |
r=.$k=.10x #.}.1#~j=.9 |
||
while. y>#r do. |
while. y>#r do. |
||
Line 262: | Line 262: | ||
end. |
end. |
||
r |
r |
||
}}</ |
}}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
< |
<syntaxhighlight lang="j"> deceptives 21 |
||
91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001</ |
91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
function deceptives(numwanted) |
function deceptives(numwanted) |
||
Line 282: | Line 282: | ||
@time println(deceptives(30)) |
@time println(deceptives(30)) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<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] |
[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] |
||
Line 289: | Line 289: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[DeceptiveNumberQ] |
||
DeceptiveNumberQ[n_Integer] := If[! PrimeQ[n], PowerMod[10, n - 1, 9 n] == 1] |
DeceptiveNumberQ[n_Integer] := If[! PrimeQ[n], PowerMod[10, n - 1, 9 n] == 1] |
||
c = 0; |
c = 0; |
||
Line 303: | Line 303: | ||
Print["The first 100:"] |
Print["The first 100:"] |
||
Multicolumn[Take[out, 100], Appearance -> "Horizontal"] |
Multicolumn[Take[out, 100], Appearance -> "Horizontal"] |
||
Print["The 1000th is: ", out[[1000]]]</ |
Print["The 1000th is: ", out[[1000]]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first 100: |
<pre>The first 100: |
||
Line 320: | Line 320: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">Rep(n)=sum(X=0,n-1,10^X) |
||
c=0 |
c=0 |
||
n=4 |
n=4 |
||
while(c<10,if(!isprime(n)&&Rep(n-1)%n==0,c=c+1;print(n));n=n+1)</ |
while(c<10,if(!isprime(n)&&Rep(n-1)%n==0,c=c+1;print(n));n=n+1)</syntaxhighlight> |
||
{{out}}<pre>91 |
{{out}}<pre>91 |
||
259 |
259 |
||
Line 341: | Line 341: | ||
Like Wren,et alias only checking odd divisors, no multiple of 3<BR> |
Like Wren,et alias only checking odd divisors, no multiple of 3<BR> |
||
Like Nigel said, no multiple of 5. |
Like Nigel said, no multiple of 5. |
||
< |
<syntaxhighlight lang="pascal">program DeceptiveNumbers; |
||
{$IfDef FPC} {$Optimization ON,ALL} {$ENDIF} |
{$IfDef FPC} {$Optimization ON,ALL} {$ENDIF} |
||
{$IfDef Windows} {$APPTYPE CONSOLE} {$ENDIF} |
{$IfDef Windows} {$APPTYPE CONSOLE} {$ENDIF} |
||
Line 458: | Line 458: | ||
{$ENDIF} |
{$ENDIF} |
||
END. |
END. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out|@TIO.RUN}} |
{{out|@TIO.RUN}} |
||
<pre> |
<pre> |
||
Line 472: | Line 472: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use Math::AnyNum qw(imod is_prime); |
use Math::AnyNum qw(imod is_prime); |
||
Line 481: | Line 481: | ||
last if 25 == @D |
last if 25 == @D |
||
} |
} |
||
print "@D\n";</ |
print "@D\n";</syntaxhighlight> |
||
{{out}} |
{{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> |
<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 488: | Line 488: | ||
{{libheader|Phix/online}} |
{{libheader|Phix/online}} |
||
You can run this online [http://phix.x10.mx/p2js/deceptive.htm here]. |
You can run this online [http://phix.x10.mx/p2js/deceptive.htm here]. |
||
<!--< |
<!--<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;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">70</span> |
<span style="color: #008080;">constant</span> <span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">70</span> |
||
Line 511: | Line 511: | ||
<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: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">))</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 533: | Line 533: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>my \R = [\+] 1, 10, 100 … *; |
||
put (2..∞).grep( {$_ % 2 && $_ % 3 && $_ % 5 && !.is-prime} ).grep( { R[$_-2] %% $_ } )[^25];</ |
put (2..∞).grep( {$_ % 2 && $_ % 3 && $_ % 5 && !.is-prime} ).grep( { R[$_-2] %% $_ } )[^25];</syntaxhighlight> |
||
{{out}} |
{{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> |
<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|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">// [dependencies] |
||
// primal = "0.3" |
// primal = "0.3" |
||
// rug = "1.15.0" |
// rug = "1.15.0" |
||
Line 563: | Line 563: | ||
repunit += 11; |
repunit += 11; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 581: | Line 581: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">say 100.by {|n| |
||
n.is_composite && (divmod(powmod(10, n-1, n)-1, 9, n) == 0) |
n.is_composite && (divmod(powmod(10, n-1, n)-1, 9, n) == 0) |
||
}.join(' ')</ |
}.join(' ')</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 592: | Line 592: | ||
=={{header|Vlang}}== |
=={{header|Vlang}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="go">import math.big |
||
fn is_prime(n int) bool { |
fn is_prime(n int) bool { |
||
Line 643: | Line 643: | ||
println(deceptive) |
println(deceptive) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 658: | Line 658: | ||
The first 62 deceptive numbers (up to 97681 though not shown in full) are found in 0.179 seconds. |
The first 62 deceptive numbers (up to 97681 though not shown in full) are found in 0.179 seconds. |
||
< |
<syntaxhighlight lang="ecmascript">/* deceptive_numbers.wren */ |
||
import "./gmp" for Mpz |
import "./gmp" for Mpz |
||
Line 679: | Line 679: | ||
} |
} |
||
System.print("The first %(limit) deceptive numbers are:") |
System.print("The first %(limit) deceptive numbers are:") |
||
System.print(deceptive)</ |
System.print(deceptive)</syntaxhighlight> |
||
{{out}} |
{{out}} |
Revision as of 23:12, 26 August 2022
You are encouraged to solve this task according to the task description, using any language you may know.
Repunits are numbers that consist entirely of repetitions of the digit one (unity). The notation Rn symbolizes the repunit made up of n ones.
Every prime p larger than 5, evenly divides the repunit Rp-1.
- E.G.
The repunit R6 is evenly divisible by 7.
111111 / 7 = 15873
The repunit R42 is evenly divisible by 43.
111111111111111111111111111111111111111111 / 43 = 2583979328165374677002583979328165374677
And so on.
There are composite numbers that also have this same property. They are often referred to as deceptive non-primes or deceptive numbers.
The repunit R90 is evenly divisible by the composite number 91 (=7*13).
- Task
- Find and show at least the first 10 deceptive numbers; composite numbers n that evenly divide the repunit Rn-1
- See also
ALGOL 68
As with the Phix, Wren and other samples we only consider odd n.
BEGIN # find repunits (all digits are 1 ) such that R(n-1) is divisible by n and n is not prime #
# R(n) is the nth repunit, so has n 1s #
PR precision 8000 PR # set precision of LONG LONG INT, enough for up to R(8000) #
PR read "primes.incl.a68" PR # include prime utilities #
[]BOOL prime = PRIMESIEVE 8000;
LONG LONG INT repunit := 111 111; # n must be odd as all repunits are odd, the lowest odd #
INT r count := 0; # non-prime is 9, so we start with repunit set to R(6) #
FOR n FROM 9 BY 2 WHILE r count < 15 DO
repunit *:= 100 +:= 11; # gets R(n-1) from R(n-3) #
IF NOT prime[ n ] THEN
IF repunit MOD n = 0 THEN
# found non-prime n which divides R(n-1) #
print( ( " ", whole( n, 0 ) ) );
r count +:= 1
FI
FI
OD
END
- Output:
91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601
Arturo
deceptive?: function [n][
and? -> not? prime? n
-> zero? (to :integer repeat "1" n-1) % n
]
cnt: 0
i: 3
while [cnt < 10][
if deceptive? i [
print i
cnt: cnt + 1
]
i: i + 2
]
- Output:
91 259 451 481 703 1729 2821 2981 3367 4141
C++
#include <gmpxx.h>
#include <iomanip>
#include <iostream>
bool is_prime(int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (int p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
int main() {
std::cout << "First 100 deceptive numbers:\n";
mpz_class repunit = 11;
for (int n = 3, count = 0; count != 100; n += 2) {
if (n % 3 != 0 && n % 5 != 0 && !is_prime(n) &&
mpz_divisible_ui_p(repunit.get_mpz_t(), n))
std::cout << std::setw(6) << n << (++count % 10 == 0 ? '\n' : ' ');
repunit *= 100;
repunit += 11;
}
}
- Output:
First 100 deceptive numbers: 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
F#
This task uses Extensible Prime Generator (F#)
// Deceptive numbers. Nigel Galloway: February 13th., 2022
Seq.unfold(fun n->Some(n|>Seq.filter(isPrime>>not)|>Seq.filter(fun n->(10I**(n-1)-1I)%(bigint n)=0I),n|>Seq.map((+)30)))(seq{1;7;11;13;17;19;23;29})|>Seq.concat|>Seq.skip 1
|>Seq.chunkBySize 10|>Seq.take 7|>Seq.iter(fun n->n|>Array.iter(printf "%7d "); printfn "")
- Output:
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
Factor
USING: io kernel lists lists.lazy math math.functions
math.primes prettyprint ;
: repunit ( m -- n ) 10^ 1 - 9 / ;
: composite ( -- list ) 4 lfrom [ prime? not ] lfilter ;
: deceptive ( -- list )
composite [ [ 1 - repunit ] keep divisor? ] lfilter ;
10 deceptive ltake [ pprint bl ] leach nl
- Output:
91 259 451 481 703 1729 2821 2981 3367 4141
Fermat
Func Rep(n)=Sigma<m=0,n-1>[10^m].;
c:=0;
n:=3;
while c<10 do
n:=n+1;
if Isprime(n)>1 and Divides(n,Rep(n-1)) then !!n; c:+; fi
od;
Go
package main
import (
"fmt"
"math/big"
"rcu"
)
func main() {
count := 0
limit := 25
n := int64(17)
repunit := big.NewInt(1111111111111111)
t := new(big.Int)
zero := new(big.Int)
eleven := big.NewInt(11)
hundred := big.NewInt(100)
var deceptive []int64
for count < limit {
if !rcu.IsPrime(int(n)) && n%3 != 0 && n%5 != 0 {
bn := big.NewInt(n)
if t.Rem(repunit, bn).Cmp(zero) == 0 {
deceptive = append(deceptive, n)
count++
}
}
n += 2
repunit.Mul(repunit, hundred)
repunit.Add(repunit, eleven)
}
fmt.Println("The first", limit, "deceptive numbers are:")
fmt.Println(deceptive)
}
- Output:
The first 25 deceptive numbers are: [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]
J
R=: (10x #. #&1)"0
deceptive=: 1&p: < 0 = ] | R@<:
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
For improved performance:
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
}}
- Output:
deceptives 21
91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001
Julia
using Primes
function deceptives(numwanted)
n, r, ret = 2, big"1", Int[]
while length(ret) < numwanted
!isprime(n) && r % n == 0 && push!(ret, n)
n += 1
r = 10r + 1
end
return ret
end
@time println(deceptives(30))
- Output:
[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] 0.296141 seconds (317.94 k allocations: 196.253 MiB, 39.26% gc time)
Mathematica/Wolfram Language
ClearAll[DeceptiveNumberQ]
DeceptiveNumberQ[n_Integer] := If[! PrimeQ[n], PowerMod[10, n - 1, 9 n] == 1]
c = 0;
out = Reap[Do[
If[DeceptiveNumberQ[i],
Sow[i];
c++;
If[c >= 1000, Break[]]
]
,
{i, 2, \[Infinity]}
]][[2, 1]];
Print["The first 100:"]
Multicolumn[Take[out, 100], Appearance -> "Horizontal"]
Print["The 1000th is: ", out[[1000]]]
- Output:
The first 100: 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 The 1000th is: 24279289
PARI/GP
Rep(n)=sum(X=0,n-1,10^X)
c=0
n=4
while(c<10,if(!isprime(n)&&Rep(n-1)%n==0,c=c+1;print(n));n=n+1)
- Output:
91259 451 481 703 1729 2821 2981 3367 4141
Pascal
Free Pascal
Brute force, not using gmp. Runtime ~ n^2.
Like Wren,et alias only checking odd divisors, no multiple of 3
Like Nigel said, no multiple of 5.
program DeceptiveNumbers;
{$IfDef FPC} {$Optimization ON,ALL} {$ENDIF}
{$IfDef Windows} {$APPTYPE CONSOLE} {$ENDIF}
uses
sysutils;
const
LIMIT = 100000;//1E6 at home takes over (5 min) now 1m10s
RepInitLen = 13; //Uint64 19 decimal digits -> max 6 digits divisor
DecimalDigits = 10*1000*1000*1000*1000;//1E13
RepLimit = (DecimalDigits-1)DIV 9;//RepInitLen '1'
type
tmyUint64 = array[0..Limit DIV RepInitLen+1] of Uint64;
var
{$Align 32}
K: tmyUint64;
{$Align 32}
MaxKIdx : Int32;
procedure OutK(const K:tmyUint64);
var
i : Uint32;
begin
For i := MaxKidx downto 0 do
begin
write(k[i]:13);
end;
writeln;
end;
function isPrime(n: UInt64):boolean;
var
p: Uint64;
begin
if n in [2,3,5,7,11,13,17,19,23,29] then
EXIT(true);
if Not ODD(n) OR ( n MOD 3 = 0) then
EXIT(false);
p := 5;
repeat
if (n mod p=0)or(n mod(p+2)=0) then
EXIT(false);
p +=6;
until p*p>n;
Exit(true);
end;
procedure ExtendRep(var K:tmyUint64;n:NativeUint);
var
q : Uint64;
i : Int32;
begin
n -= MaxKidx*RepInitLen;
i := MaxKidx;
while RepInitLen<=n do
begin
K[i] := RepLimit;
inc(i);
dec(n,RepInitLen);
end;
if n = 0 then
Exit;
MaxKidx := i;
q := 1;
while n<RepInitLen do
begin
q *= 10;
inc(n);
end;
K[i] := RepLimit DIV q;
end;
function GetModK(const K:tmyUint64;n:Uint64):NativeUint;
var
r,q : Uint64;
i : Uint32;
Begin
r := 0;
For i := MaxKidx downto 0 do
begin
q := K[i]+r*DecimalDigits;
r := q MOD n;
end;
Exit(r)
end;
const
NextNotMulOF35 : array[0..7] of byte = (6,4,2,4,2,4,6,2);
var
i,cnt,idx35 : UInt64;
BEGIN
fillchar(K,SizeOF(K),#0);
MaxKIdx:= 0;
cnt := 0;
i := 1;
idx35 := 0;
repeat
inc(i,NextNotMulOF35[idx35]);
IF i > LIMIT then
BREAK;
idx35 := (idx35+1) AND 7;
if isprime(i) then
continue;
ExtendRep(k,i-1);
IF GetModK(K,i)=0 then
Begin
inc(cnt);
write(i:6,',');
if cnt Mod 10 = 0 then
writeln;
end;
until false;
{$IfDef Windows}
readln;
{$ENDIF}
END.
- @TIO.RUN:
Real time: 1.009 s User time: 0.971 s Sys. time: 0.033 s CPU share: 99.43 % 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,
Perl
use strict;
use warnings;
use Math::AnyNum qw(imod is_prime);
my($x,@D) = 2;
while ($x++) {
push @D, $x if 1 == $x%2 and !is_prime $x and 0 == imod(1x($x-1),$x);
last if 25 == @D
}
print "@D\n";
- Output:
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
Phix
You can run this online here.
with javascript_semantics constant limit = 70 atom t0 = time() include mpfr.e mpz repunit = mpz_init(0) integer n = 1, count = 0 printf(1,"The first %d deceptive numbers are:\n",limit) while count<limit do -- No repunit is ever divisible by 2 or 5 since it ends in 1. -- If n is 3*k, sum(digits(repunit))=3*k-1, not divisible by 3. -- Hence only check odd and hop any multiples of 3 or 5. n += 2 mpz_mul_si(repunit,repunit,100) mpz_add_si(repunit,repunit,11) if gcd(n,3*5)=1 and not is_prime(n) and mpz_divisible_ui_p(repunit,n) then count += 1 printf(1," %7d%n",{n,remainder(count,10)=0}) end if end while printf(1,"%s\n",elapsed(time()-t0))
- Output:
The first 70 deceptive numbers are: 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 1.6s
Extending the limit to 100 (matching the C++ and Rust entries) is no problem:
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 4.2s -- (7.3s under pwa/p2js)
Raku
my \R = [\+] 1, 10, 100 … *;
put (2..∞).grep( {$_ % 2 && $_ % 3 && $_ % 5 && !.is-prime} ).grep( { R[$_-2] %% $_ } )[^25];
- Output:
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
Rust
// [dependencies]
// primal = "0.3"
// rug = "1.15.0"
fn main() {
println!("First 100 deceptive numbers:");
use rug::Integer;
let mut repunit = Integer::from(11);
let mut n: u32 = 3;
let mut count = 0;
while count != 100 {
if n % 3 != 0 && n % 5 != 0 && !primal::is_prime(n as u64) && repunit.is_divisible_u(n) {
print!("{:6}", n);
count += 1;
if count % 10 == 0 {
println!();
} else {
print!(" ");
}
}
n += 2;
repunit *= 100;
repunit += 11;
}
}
- Output:
First 100 deceptive numbers: 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
Sidef
say 100.by {|n|
n.is_composite && (divmod(powmod(10, n-1, n)-1, 9, n) == 0)
}.join(' ')
- Output:
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
Vlang
import math.big
fn is_prime(n int) bool {
if n < 2 {
return false
} else if n%2 == 0 {
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
}
d += 2
if n%d == 0 {
return false
}
d += 4
}
return true
}
}
fn main() {
mut count := 0
limit := 25
mut n := i64(17)
mut repunit := big.integer_from_i64(1111111111111111)
mut t := big.integer_from_int(0)
zero := big.integer_from_int(0)
eleven := big.integer_from_int(11)
hundred := big.integer_from_int(100)
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
if t == zero {
deceptive << n
count++
}
}
n += 2
repunit = repunit * hundred
repunit = repunit + eleven
}
println("The first $limit deceptive numbers are:")
println(deceptive)
}
- Output:
The first 25 deceptive numbers are: [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]
Wren
An embedded program so we can use GMP. Takes 0.019 seconds to find the first 25 deceptive numbers.
The first 62 deceptive numbers (up to 97681 though not shown in full) are found in 0.179 seconds.
/* deceptive_numbers.wren */
import "./gmp" for Mpz
import "./math" for Int
var count = 0
var limit = 25
var n = 17
var repunit = Mpz.from(1111111111111111)
var deceptive = []
while (count < limit) {
if (!Int.isPrime(n) && n % 3 != 0 && n % 5 != 0) {
if (repunit.isDivisibleUi(n)) {
deceptive.add(n)
count = count + 1
}
}
n = n + 2
repunit.mul(100).add(11)
}
System.print("The first %(limit) deceptive numbers are:")
System.print(deceptive)
- Output:
The first 25 deceptive numbers are: [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]