Deceptive numbers

Deceptive numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Repunits are numbers that consist entirely of repetitions of the digit one (unity). The notation R_n symbolizes the repunit made up of n ones.

Every prime p larger than 5, evenly divides the the repunit R_p-1.

E.G.

The repunit R₆ is evenly divisible by 7.

111111 / 7 = 15873

The repunit R₄₂ 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 R₉₀ is evenly divisible by the composite number 91.

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 / 91 = 1221001221001221001221001221001221001221001221001221001221001221001221001221001221001221

Task

• Find and show at least the first 10 deceptive numbers; composite numbers n that evenly divide the repunit R_n-1

See also

• Numbers Aplenty - Deceptive numbers
• OEIS:A000864 - Deceptive nonprimes: composite numbers k that divide the repunit R_{k-1}

Factor

Works with: Factor version 0.99 2021-06-02

<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

Library: Phix/online

You can run this online here.

with javascript_semantics
constant limit = 25
atom t0 = time()
include mpfr.e
mpz z = mpz_init()
integer n = 3, count = 0
printf(1,"The first %d deceptive numbers are:\n",limit)
while count<limit do
    if not is_prime(n) and remainder(n,3)!=0 then
        mpz_set_str(z,repeat('1',n-1))
        if mpz_divisible_ui_p(z, n)!=0 then
            printf(1," %d",n)
            count += 1
        end if
    end if
    n += 2
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
2.3s

Raku

<lang perl6>put (2..∞).hyper.grep( {$_ % 2 && !.is-prime} ).grep( { (1 x ($_ - 1)) %% $_ } )[^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

Library: Wren-gmp

Library: Wren-math

An embedded program so we can use GMP. Takes 127 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 = 25 var deceptive = [] while (count < limit) {

   if (!Int.isPrime(n) && n % 3 != 0) {
       var repunit = Mpz.fromStr("1" * (n-1))
       if (repunit.isDivisibleUi(n)) {
           deceptive.add(n)
           count = count + 1
       }
   }
   n = n + 2

} 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]