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)

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]