I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Deceptive numbers

Deceptive numbers
You are encouraged to solve this task according to the task description, using any language you may know.

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

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

E.G.

The repunit R6 is evenly divisible by 7.

111111 / 7 = 15873

The repunit R42 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 R90 is evenly divisible by the composite number 91 (=7*13).

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 / 91 = 1221001221001221001221001221001221001221001221001221001221001221001221001221001221001221

• Find and show at least the first 10 deceptive numbers; composite numbers n that evenly divide the repunit Rn-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.

`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    ODEND`
Output:
``` 91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601
```

## Arturo

`deceptive?: function [n][    and? -> not? prime? n         -> zero? (to :integer repeat "1" n-1) % n] cnt: 0i: 3 while [cnt < 10][    if deceptive? i [        print i        cnt: cnt + 1    ]    i: i + 2]`
Output:
```91
259
451
481
703
1729
2821
2981
3367
4141```

## C++

Library: GMP
`#include <gmpxx.h> #include <iomanip>#include <iostream> bool is_prime(int n) {    if (n < 2)        return false;    if (n % 2 == 0)        return n == 2;    if (n % 3 == 0)        return n == 3;    for (int p = 5; p * p <= n; p += 4) {        if (n % p == 0)            return false;        p += 2;        if (n % p == 0)            return false;    }    return true;} int main() {    std::cout << "First 100 deceptive numbers:\n";    mpz_class repunit = 11;    for (int n = 3, count = 0; count != 100; n += 2) {        if (n % 3 != 0 && n % 5 != 0 && !is_prime(n) &&            mpz_divisible_ui_p(repunit.get_mpz_t(), n))            std::cout << std::setw(6) << n << (++count % 10 == 0 ? '\n' : ' ');        repunit *= 100;        repunit += 11;    }}`
Output:
```First 100 deceptive numbers:
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
118301 118957 122221 126217 128713 130351 131821 134821 134863 137137
137149 138481 139231 145181 147001 148417 152551 158497 162401 164761
166499 170017 172081 179881 188191 188269 188461 188501 196651 201917
```

## F#

This task uses Extensible Prime Generator (F#)

` // Deceptive numbers. Nigel Galloway: February 13th., 2022Seq.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 "") `
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
`USING: io kernel lists lists.lazy math math.functionsmath.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`
Output:
```91 259 451 481 703 1729 2821 2981 3367 4141
```

## Fermat

`Func Rep(n)=Sigma<m=0,n-1>[10^m].;c:=0;n:=3;while c<10 do    n:=n+1;    if Isprime(n)>1 and Divides(n,Rep(n-1)) then !!n; c:+; fiod;`

## Go

Translation of: Wren
Library: Go-rcu
`package main import (    "fmt"    "math/big"    "rcu") func main() {    count := 0    limit := 25    n := int64(17)    repunit := big.NewInt(1111111111111111)    t := new(big.Int)    zero := new(big.Int)    eleven := big.NewInt(11)    hundred := big.NewInt(100)    var deceptive []int64    for count < limit {        if !rcu.IsPrime(int(n)) && n%3 != 0 && n%5 != 0 {            bn := big.NewInt(n)            if t.Rem(repunit, bn).Cmp(zero) == 0 {                deceptive = append(deceptive, n)                count++            }        }        n += 2        repunit.Mul(repunit, hundred)        repunit.Add(repunit, eleven)    }    fmt.Println("The first", limit, "deceptive numbers are:")    fmt.Println(deceptive)}`
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]
```

## J

`R=: (10x #. #&1)"0deceptive=: 1&p: < 0 = ] | [email protected]<:    2+I.deceptive 2+i.1000091 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001`

For improved performance:

`deceptives=: {{  r=.\$k=.10x #.}.1#~j=.9  while. y>#r do.    if. 0<2|j do.      if. 0<5|j do.        if. 0=1 p:j do.          if. 0=0]j|k do.            r=. r, j          end.        end.      end.    end.    k=. 1 10x p.k    j=. j+1  end.  r}}`
Output:
`   deceptives 2191 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 10001`

## 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 retend @time println(deceptives(30)) `
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)
```

## PARI/GP

`Rep(n)=sum(X=0,n-1,10^X)c=0n=4while(c<10,if(!isprime(n)&&Rep(n-1)%n==0,c=c+1;print(n));n=n+1)`
Output:
```91
259
451
481
703
1729
2821
2981
3367
4141

```

## 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.

`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. `
@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

`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";`
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)
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
```

Extending the limit to 100 (matching the C++ and Rust entries) is no problem:

```  118301  118957  122221  126217  128713  130351  131821  134821  134863  137137
137149  138481  139231  145181  147001  148417  152551  158497  162401  164761
166499  170017  172081  179881  188191  188269  188461  188501  196651  201917
4.2s -- (7.3s under pwa/p2js)
```

## Raku

`my \R = [\+] 1, 10, 100 … *;put (2..∞).grep( {\$_ % 2 && \$_ % 3 && \$_ % 5 && !.is-prime} ).grep( { R[\$_-2] %% \$_ } )[^25];`
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`

## Rust

`// [dependencies]// primal = "0.3"// rug = "1.15.0" fn main() {    println!("First 100 deceptive numbers:");    use rug::Integer;    let mut repunit = Integer::from(11);    let mut n: u32 = 3;    let mut count = 0;    while count != 100 {        if n % 3 != 0 && n % 5 != 0 && !primal::is_prime(n as u64) && repunit.is_divisible_u(n) {            print!("{:6}", n);            count += 1;            if count % 10 == 0 {                println!();            } else {                print!(" ");            }        }        n += 2;        repunit *= 100;        repunit += 11;    }}`
Output:
```First 100 deceptive numbers:
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
118301 118957 122221 126217 128713 130351 131821 134821 134863 137137
137149 138481 139231 145181 147001 148417 152551 158497 162401 164761
166499 170017 172081 179881 188191 188269 188461 188501 196651 201917
```

## Sidef

`say 100.by {|n|    n.is_composite && (divmod(powmod(10, n-1, n)-1, 9, n) == 0)}.join(' ')`
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 118301 118957 122221 126217 128713 130351 131821 134821 134863 137137 137149 138481 139231 145181 147001 148417 152551 158497 162401 164761 166499 170017 172081 179881 188191 188269 188461 188501 196651 201917
```

## Vlang

Translation of: Go
`import math.big fn is_prime(n int) bool {    if n < 2 {        return false    } else if n%2 == 0 {        return n == 2    } else if n%3 == 0 {        return n == 3    } else {        mut d := 5        for d*d <= n {            if n%d == 0 {                return false            }            d += 2            if n%d == 0 {                return false            }            d += 4        }        return true    }} fn main() {    mut count := 0    limit := 25    mut n := i64(17)    mut repunit := big.integer_from_i64(1111111111111111)    mut t := big.integer_from_int(0)    zero := big.integer_from_int(0)    eleven := big.integer_from_int(11)    hundred := big.integer_from_int(100)    mut deceptive := []i64{}    for count < limit {        if !is_prime(int(n)) && n%3 != 0 && n%5 != 0 {            bn := big.integer_from_i64(n)            t = repunit % bn            if t == zero {                deceptive << n                count++            }        }        n += 2        repunit = repunit * hundred        repunit = repunit + eleven    }    println("The first \$limit deceptive numbers are:")    println(deceptive)} `
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]
```

## 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.

`/* deceptive_numbers.wren */ import "./gmp" for Mpzimport "./math" for Int var count = 0var limit = 25var n = 17var 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)`
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]
```