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)

Pascal

Free Pascal

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

 sysutils;

const

 LIMIT = 100000;//1E6 takes over 5 min
 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

 K: tmyUint64;
 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;

var

 i,j,cnt : UInt64;

BEGIN

 fillchar(K,SizeOF(K),#0);
 MaxKIdx:= 0;
 cnt := 0;
 i := 5;
 For j := 3 to (LIMIT-1) DIV 2 do
 begin
   inc(i,2);
   if isprime(i) OR (i mod 3=0) 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;
 end;
{$IfDef Windows}
readln;
{$ENDIF}

END. </lang>

@TIO.RUN:

Real time: 1.338 s User time: 1.293 s Sys. time: 0.037 s CPU share: 99.42 %
    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 = 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]