Deceptive numbers

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 (=7*13).

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

This task uses Extensible Prime Generator (F#) <lang fsharp> // Deceptive numbers. Nigel Galloway: February 13th., 2022 Seq.unfold(fun n->Some(n|>Seq.filter(isPrime>>not)|>Seq.filter(fun n->(10I**(n-1)-1I)%(bigint n)=0I),n|>Seq.map((+)30)))(seq{1;7;11;13;17;19;23;29})|>Seq.concat|>Seq.skip 1 |>Seq.chunkBySize 10|>Seq.take 7|>Seq.iter(fun n->n|>Array.iter(printf "%7d "); printfn "") </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
  22321   24013   24661   27613   29341   34133   34441   35113   38503   41041
  45527   46657   48433   50851   50881   52633   54913   57181   63139   63973
  65311   66991   67861   68101   75361   79003   82513   83119   94139   95161
  97273   97681  100001  101101  101491  102173  108691  113201  115627  115921

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>

For improved performance:

<lang J>deceptives=: Template:R=.$k=.10x</lang>

Output:

<lang J> deceptives 21 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)

Pascal

Free Pascal

Brute force, not using gmp. Runtime ~ n^2.
Like Wren,et alias only checking odd divisors, no multiple of 3
Like Nigel said, no multiple of 5. <lang pascal>program DeceptiveNumbers; {$IfDef FPC} {$Optimization ON,ALL} {$ENDIF} {$IfDef Windows} {$APPTYPE CONSOLE} {$ENDIF} uses

 sysutils;

const

 LIMIT = 100000;//1E6 at home takes over (5 min) now 1m10s
 RepInitLen = 13; //Uint64 19 decimal digits -> max 6 digits divisor
 DecimalDigits = 10*1000*1000*1000*1000;//1E13
 RepLimit = (DecimalDigits-1)DIV 9;//RepInitLen '1'

type

 tmyUint64 = array[0..Limit DIV RepInitLen+1] of Uint64;

var

 {$Align 32}
 K: tmyUint64;
 {$Align 32}
 MaxKIdx : Int32;

procedure OutK(const K:tmyUint64); var

 i : Uint32;

begin

 For i := MaxKidx downto 0 do
 begin
   write(k[i]:13);
 end;
 writeln;

end;

function isPrime(n: UInt64):boolean; var

p: Uint64;

begin

 if n in [2,3,5,7,11,13,17,19,23,29] then
   EXIT(true);

 if Not ODD(n) OR ( n MOD 3 = 0) then
   EXIT(false);
 p := 5;
 repeat
   if (n mod p=0)or(n mod(p+2)=0) then
     EXIT(false);
   p +=6;
 until p*p>n;
 Exit(true);

end;

procedure ExtendRep(var K:tmyUint64;n:NativeUint); var

 q : Uint64;
 i : Int32;

begin

 n -= MaxKidx*RepInitLen;
 i := MaxKidx;
 while RepInitLen<=n do
 begin
   K[i] := RepLimit;
   inc(i);
   dec(n,RepInitLen);
 end;
 if n = 0 then
   Exit;
 MaxKidx := i;
 q := 1;
 while n<RepInitLen do
 begin
   q *= 10;
   inc(n);
 end;
 K[i] := RepLimit DIV q;

end;

function GetModK(const K:tmyUint64;n:Uint64):NativeUint; var

 r,q : Uint64;
 i : Uint32;

Begin

 r := 0;
 For i := MaxKidx downto 0 do
 begin
   q := K[i]+r*DecimalDigits;
   r := q MOD n;
 end;
 Exit(r)

end;

const

 NextNotMulOF35 : array[0..7] of byte = (6,4,2,4,2,4,6,2);

var

 i,cnt,idx35 : UInt64;

BEGIN

 fillchar(K,SizeOF(K),#0);
 MaxKIdx:= 0;
 cnt := 0;
 i := 1;
 idx35 := 0;
 repeat
   inc(i,NextNotMulOF35[idx35]);
   IF i > LIMIT then
     BREAK;
   idx35 := (idx35+1) AND 7;
   if isprime(i) then
     continue;
   ExtendRep(k,i-1);
   IF GetModK(K,i)=0 then
   Begin
     inc(cnt);
     write(i:6,',');
     if cnt Mod 10 = 0 then
       writeln;
   end;
 until false;
{$IfDef Windows}
readln;
{$ENDIF}

END. </lang>

@TIO.RUN:

Real time: 1.009 s User time: 0.971 s Sys. time: 0.033 s CPU share: 99.43 %

    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,
 22321, 24013, 24661, 27613, 29341, 34133, 34441, 35113, 38503, 41041,
 45527, 46657, 48433, 50851, 50881, 52633, 54913, 57181, 63139, 63973,
 65311, 66991, 67861, 68101, 75361, 79003, 82513, 83119, 94139, 95161,
 97273, 97681,

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 = 70
atom t0 = time()
include mpfr.e
mpz repunit = mpz_init(0)
integer n = 1, count = 0
printf(1,"The first %d deceptive numbers are:\n",limit)
while count<limit do
    -- No repunit is ever divisible by 2 or 5 since it ends in 1.
    -- If n is 3*k, sum(digits(repunit))=3*k-1, not divisible by 3.
    -- Hence only check odd and hop any multiples of 3 or 5.
    n += 2
    mpz_mul_si(repunit,repunit,100)
    mpz_add_si(repunit,repunit,11)
    if gcd(n,3*5)=1 
    and not is_prime(n)
    and mpz_divisible_ui_p(repunit,n) then
        count += 1
        printf(1," %7d%n",{n,remainder(count,10)=0})
    end if
end while
printf(1,"%s\n",elapsed(time()-t0))

Output:

The first 70 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   14911   15211   15841   19201   21931
   22321   24013   24661   27613   29341   34133   34441   35113   38503   41041
   45527   46657   48433   50851   50881   52633   54913   57181   63139   63973
   65311   66991   67861   68101   75361   79003   82513   83119   94139   95161
   97273   97681  100001  101101  101491  102173  108691  113201  115627  115921
1.6s

Raku

<lang perl6>my \R = [\+] 1, 10, 100 … *; put (2..∞).grep( {$_ % 2 && $_ % 3 && $_ % 5 && !.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.019 seconds to find the first 25 deceptive numbers.

The first 62 deceptive numbers (up to 97681 though not shown in full) are found in 0.179 seconds. <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 && n % 5 != 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]