Deceptive numbers: Difference between revisions
m →{{header|Phix}}: removed two unnecessary "!=0"s |
→{{header|Wren}}: Moved to initializing repunits from integers rather than strings - 10 x speedup. |
||
Line 130:
{{libheader|Wren-gmp}}
{{libheader|Wren-math}}
An embedded program so we can use GMP. Takes 0.
<lang ecmascript>/* deceptive_numbers.wren */
Line 137:
var count = 0
var limit =
var n =
var repunit = Mpz.from(1111111111111111)
var deceptive = []
while (count < limit) {
if (!Int.isPrime(n) && n % 3 != 0) {
if (repunit.isDivisibleUi(n)) {
deceptive.add(n)
Line 150 ⟶ 149:
}
n = n + 2
}
System.print("The first %(limit) deceptive numbers are:")
|
Revision as of 17:32, 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
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 = 80 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]