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}

ALGOL 68

Works with: ALGOL 68G version Any - tested with release 3.0.1.win32

As with the Phix, Wren and other samples we only consider odd n.

Library: ALGOL 68-primes

<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

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 

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)

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(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

Library: Wren-gmp

Library: Wren-math

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]