Deceptive numbers: Difference between revisions
(Added Algol 68) |
m (→{{header|ALGOL 68}}: comments) |
||
Line 44: | Line 44: | ||
<lang algol68>BEGIN # find repunits (all digits are 1 ) such that R(n-1) is divisible by n and n is not prime # |
<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 # |
PR precision 8000 PR # set precision of LONG LONG INT, enough for upto R(8000) # |
||
PR read "primes.incl.a68" PR # include prime utilities # |
PR read "primes.incl.a68" PR # include prime utilities # |
||
[]BOOL prime = PRIMESIEVE 8000; |
[]BOOL prime = PRIMESIEVE 8000; |
||
LONG LONG INT repunit := 0; |
LONG LONG INT repunit := 0; |
Revision as of 19:23, 11 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
<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 upto R(8000) # PR read "primes.incl.a68" PR # include prime utilities # []BOOL prime = PRIMESIEVE 8000; LONG LONG INT repunit := 0; INT r count := 0; FOR n FROM 2 WHILE r count < 15 DO repunit *:= 10 +:= 1; 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
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)
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 z = mpz_init(11) integer n = 3, count = 0 printf(1,"The first %d deceptive numbers are:\n",limit) while count<25 do if not is_prime(n) and remainder(n,3) then if mpz_divisible_ui_p(z,n) then printf(1," %d",n) count += 1 end if end if n += 2 mpz_mul_si(z,z,100) mpz_add_si(z,z,11) 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 && !.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.021 seconds to find the first 25 deceptive numbers. <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) { 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]