Deceptive numbers: Difference between revisions
Thundergnat (talk | contribs) m →{{header|Raku}}: well duh. obvious once it's pointed out |
m →{{header|Phix}}: added the mod 5 check and a comment |
||
Line 269:
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</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: #004080;">mpz</span> <span style="color: #000000;">
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">
<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;">"The first %d deceptive numbers are:\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">limit</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><</span><span style="color: #000000;">
<span style="color: #000080;font-style:italic;">-- No repunit is ever divisible by 2 or 5 since it ends in 1.
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>▼
-- If n is 3*k, sum(digits(repunit))=3*k-1, not divisible by 3.
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_divisible_ui_p</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>▼
-- Hence only check odd and hop any multiples of 3 or 5.</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;">" %d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>▼
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>▼
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>▼
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">2</span>
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">
<span style="color: #7060A8;">mpz_add_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">
▲ <span style="color: #008080;">if
<span style="color: #008080;">and</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">is_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</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;">"\n%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>
|
Revision as of 11:25, 13 February 2022
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 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.
- 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.
<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 # 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</lang>
- Output:
91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601
Factor
<lang 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</lang>
- Output:
91 259 451 481 703 1729 2821 2981 3367 4141
J
<lang 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</lang>
Julia
<lang 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))
</lang>
- 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)
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.
<lang pascal>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. </lang>
- @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
<lang 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";</lang>
- 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 = 25 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 printf(1," %d",n) count += 1 end if end while printf(1,"\n%s\n",elapsed(time()-t0))
- 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 0.2s
Raku
<lang perl6>my \R = [\+] 1, 10, 100 … *; put (2..∞).grep( {$_ % 2 && $_ % 3 && $_ % 5 && !.is-prime} ).grep( { R[$_-2] %% $_ } )[^25];</lang>
- 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
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. <lang ecmascript>/* 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)</lang>
- 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]