Jump to content

Deceptive numbers

From Rosetta Code
Task
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 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


Task
  • Find and show at least the first 10 deceptive numbers; composite numbers n that evenly divide the repunit Rn-1


See also



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

ALGOL W

Based on the second Wren sample - finds the numbers without needing large integers - see the Talk page.

begin % find deceptive numbers - repunits R(n) evenly divisible by composite    %
      % numbers and n+1; see the task talk page based on the second Wren sample %

    % returns true if n is an odd prime, false otherwise, uses trial division   %
    logical procedure isOddPrime ( integer value n ) ;
        begin
            logical prime;
            integer f, f2, toNext;
            prime  := true;
            f      :=  3;
            f2     :=  9;
            toNext := 16;        % note: ( 2n + 1 )^2 - ( 2n - 1 )^2 = 8n       %
            while f2 <= n and prime do begin
                prime  := n rem f not = 0;
                f      := f + 2;
                f2     := toNext;
                toNext := toNext + 8
             end while_f2_le_n_and_prime ;
             prime
        end isOddPrime ;

    begin % -- task %
        integer n, count;
        count :=  0;
        n     := 47;
        while begin n := n + 2;
                    count < 25
              end
        do    begin
              if n rem 3 not = 0 and n rem 5 not = 0 and not isOddPrime( n ) then begin
                  integer mp;
                  mp := 10;
                  for p := 2 until n - 1 do mp := ( mp * 10 ) rem n;
                  if mp = 1 then begin
                      count := count + 1;
                      writeon( i_w := 5, s_w := 0, " ", n );
                      if count rem 10 = 0 then write()
                  end if_mp_eq_1
              end if_have_a_candidate
        end while_count_lt_50
    end task

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

Amazing Hopper

Translation of: C
#include <jambo.h>

#prototype  isdeceptive(_X_)
#prototype  modulepow(_X_,_Y_,_Z_)
#synon  _isdeceptive   Isdeceptive
#synon  _modulepow     ModulePow
#define Breaking    Goto(exit)
Main
    i = 49, c=0
    Iterator ( ++i, #(c <> 10), \
        Print only if ( Is deceptive 'i', Set 'i,"\n"'; ++c ) )
End

Subrutines 

is deceptive ( n )
    x=7
    And( Bitand(n,1), And( Mod(n,3), Mod(n,5) )), do {
        Iterator( x+=6, #( (x*x) <= n ),\
             #(!( (n%x) && (n%(x+4)) )), do{ \
                Module Pow (10, Minus one(n), n), Is equal to '1', Breaking } )
    }
    Set '0'
    exit:
Return

module pow(b, e, m)
    Loop for (p = 1, e,  e >>= 1)
        Bitand(e, 1), do{ #( p = (p * b) % m ) }
        #( b = (b * b) % m )
    Next
Return (p)
Output:
91 
259
451
481
703
1729
2821
2981
3367
4141

Arturo

deceptive?: function [n][
    and? -> not? prime? n
         -> zero? (to :integer repeat "1" n-1) % n
]

cnt: 0
i: 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

AWK

function modpow(b, e, m,   r) {
    for (r = 1; e > 0; e = int(e / 2)) {
        if (e % 2 == 1)
            r = r * b % m
        b = b * b % m
    }
    return r
}

function is_pseudo(n,   i, p, r) {
    if (modpow(10, n - 1, n) == 1) {
        r = int(sqrt(n))
        while ((p = primes[++i]) <= r)
            if (n % p == 0)
                return 1
        primes[++l] = n
    }
    return 0
}

BEGIN {
    primes[l = 1] = n = 7
    split("4 2 4 2 4 6 2 6", wheel)

    do if (is_pseudo(n += wheel[i = i % 8 + 1])) {
        printf " %u", n
        ++c
    } while (c != 50)
    print
}
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

bc

/* modular exponentiation */
define p(b, e, m) {
    auto r
    for (r = 1; e > 0; e /= 2) {
        if (e % 2 == 1) r = r * b % m
        b = b * b % m
    }
    return(r)
}

/* cache for the primes found */
p[0] = 7

define d(n) {
    auto i, p, r;
    if (p(10, n - 1, n) == 1) {
        for (r = sqrt(n); (p = p[i]) <= r; ++i) if (n % p == 0) return(1)
        p[++l] = n
    }
    return(0)
}

/* wheel to skip multiples of 2, 3, and 5 */
w[0] = 4
w[1] = 2
w[2] = 4
w[3] = 2
w[4] = 4
w[5] = 6
w[6] = 2
w[7] = 6

for (n = p[0]; c != 10; i = (i + 1) % 8) {
    if (d(n += w[i]) == 1) {
        n
        c += 1
    }
}
Output:
91
259
451
481
703
1729
2821
2981
3367
4141

C

#include <inttypes.h>
#include <stdio.h>

uint32_t modpow(uint32_t b, uint32_t e, uint32_t m)
{
    uint32_t p;
    for (p = 1; e; e >>= 1) {
        if (e & 1)
            p = (uint64_t)p * b % m;
        b = (uint64_t)b * b % m;
    }
    return p;
}

int is_deceptive(uint32_t n)
{
    uint32_t x;
    if (n & 1 && n % 3 && n % 5 && modpow(10, n - 1, n) == 1) {
        for (x = 7; x * x <= n; x += 6) {
            if (!(n % x && n % (x + 4)))
                return 1;
        }
    }
    return 0;
}

int main(void)
{
    uint32_t n = 49;
    unsigned int c;
    for (c = 0; c != 500; ++n) {
        if (is_deceptive(n)) {
            printf(" %" PRIu32, n);
            ++c;
        }
    }
    return 0;
}
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 216001 216931 225589 226273 229633 231337 234421 237169 237817 245491 247753 248677 250717 251251 252601 253099 269011 269569 274231 281821 286903 287749 287809 294409 298033 301081 302177 304057 314821 334153 340561 341503 346801 351809 357641 364277 366337 372731 385003 390313 391141 399001 401401 410041 413339 420343 437251 451091 455971 458641 463241 463489 481601 488881 489997 491063 492101 497377 497503 497927 505363 507529 509971 511969 512461 520801 522349 530881 532171 552721 567721 585631 586993 588193 589537 595231 597871 601657 603961 607321 632641 634351 642001 658801 665401 670033 679861 710533 721801 736291 741751 748657 749521 754369 764491 765703 827281 838201 841633 847693 852841 853381 868001 873181 880237 886033 903169 906193 909709 924001 929633 963857 974611 976873 981317 989017 997633 997981 999001 1004329 1005697 1024651 1033669 1038331 1039441 1039849 1041043 1042417 1056331 1069993 1080697 1081649 1082809 1090051 1096681 1111111 1128871 1141141 1146401 1152271 1163801 1167607 1168513 1169101 1171261 1182721 1193221 1242241 1242571 1251949 1267801 1268551 1272271 1275347 1279201 1287937 1294411 1298737 1306369 1308853 1336699 1362061 1376299 1394171 1398101 1408849 1419607 1446241 1446661 1450483 1461241 1462441 1463749 1492663 1498981 1504321 1531711 1543381 1551941 1569457 1576381 1583821 1590751 1602601 1615681 1703221 1705621 1708993 1711381 1711601 1719601 1731241 1739089 1748921 1756351 1758121 1769377 1772611 1773289 1792081 1803413 1809697 1810513 1826209 1840321 1846681 1850017 1857241 1863907 1869211 1876393 1884961 1887271 1892143 1894651 1907851 1909001 1918201 1922801 1926761 1942957 1943341 1945423 1953671 1991821 2024641 2030341 2044657 2056681 2063971 2085301 2100901 2113921 2146957 2161501 2165801 2171197 2171401 2184931 2190931 2194973 2203321 2205967 2215291 2237017 2278001 2290289 2299081 2305633 2314201 2337301 2358533 2371681 2386141 2392993 2406401 2424731 2432161 2433601 2455921 2463661 2503501 2508013 2512441 2524801 2525909 2539183 2553061 2563903 2585701 2603381 2628073 2630071 2658433 2694601 2699431 2704801 2719981 2765713 2795519 2824061 2868097 2879317 2887837 2899351 2916511 2949991 2960497 2976487 2987167 3005737 3057601 3076481 3084577 3117547 3125281 3140641 3146221 3167539 3186821 3209053 3225601 3247453 3255907 3270403 3362083 3367441 3367771 3369421 3387781 3398921 3400013 3426401 3429889 3471071 3488041 3506221 3520609 3523801 3536821 3537667 3581761 3593551 3596633 3658177 3677741 3678401 3740737 3781141 3788851 3815011 3817681 3828001 3850771 3862207 3879089 3898129 3913003 3930697 3947777 3985921 4005001 4010401 4014241 4040281 4040881 4064677 4074907 4077151 4099439 4100041 4119301 4151281 4181921 4182739 4209661 4225057 4234021 4255903 4260301 4316089 4326301 4335241 4360801 4363261 4363661 4372771 4373461 4415251 4415581 4454281 4463641 4469471 4469551 4499701 4504501 4543621 4627441 4630141 4637617 4762381 4767841 4784689 4806061 4863127 4903921 4909177 4909411 4909913 4917781 5031181 5045401 5049001 5056051 5122133 5148001 5160013 5180593 5197837 5203471

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

Without external libraries

#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>

uint64_t power_modulus(uint64_t base, uint64_t exponent, const uint64_t& modulus) {
	if ( modulus == 1 ) {
		return 0;
	}

	base %= modulus;
	uint64_t result = 1;
	while ( exponent > 0 ) {
		if ( ( exponent & 1 ) == 1 ) {
			result = ( result * base ) % modulus;
		}
		base = ( base * base ) % modulus;
		exponent >>= 1;
	}
	return result;
}

bool is_deceptive(const uint32_t& n) {
	if ( n % 2 != 0 && n % 3 != 0 && n % 5 != 0 && power_modulus(10, n - 1, n) == 1 ) {
		for ( uint32_t divisor = 7; divisor < sqrt(n); divisor += 6 ) {
			if ( n % divisor == 0 || n % ( divisor + 4 ) == 0 ) {
				return true;
			}
		}
	}
	return false;
}

int main() {
	uint32_t n = 7;
	uint32_t count = 0;
	while ( count < 100 ) {
		if ( is_deceptive(n) ) {
			std::cout << std::setw(6) << n << ( ++count % 10 == 0 ? "\n" : " " );
		}
		n += 1;
	}
}
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

EasyLang

Translation of: C
func modpow b e m .
   r = 1
   while e > 0
      if e mod 2 = 1
         r = r * b mod m
      .
      b = b * b mod m
      e = e div 2
   .
   return r
.
func is_deceptive n .
   if n mod 2 = 1 and n mod 3 <> 0 and n mod 5 <> 0
      if modpow 10 (n - 1) n = 1
         x = 7
         while x * x <= n
            if n mod x = 0 or n mod (x + 4) = 0
               return 1
            .
            x += 6
         .
      .
   .
.
while cnt < 10
   n += 1
   if is_deceptive n = 1
      write n & " "
      cnt += 1
   .
.
Output:
91 259 451 481 703 1729 2821 2981 3367 4141 

F#

This task uses Extensible Prime Generator (F#)

// 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 "")
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.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
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:+; fi
od;

FreeBASIC

Translation of: XPLo
Function ModPow(b As Uinteger, e As Uinteger, m As Uinteger) As Uinteger
    Dim As Uinteger p = 1
    While e <> 0
        If (e And 1) Then p = (p*b) Mod m
        b = (b*b) Mod m
        e Shr= 1
    Wend
    Return p
End Function

Function isDeceptive(n As Uinteger) As Uinteger
    Dim As Uinteger x
    If (n And 1) <> 0 Andalso (n Mod 3) <> 0 Andalso (n Mod 5) <> 0 Then
        x = 7
        While x*x <= n
            If (n Mod x) = 0 Orelse (n Mod (x+4)) = 0 Then Return (ModPow(10, n-1, n) = 1)
            x += 6
        Wend
    End If
    Return 0
End Function

Dim As Uinteger c = 0, i = 49
While c <> 41 ' limit for signed 32-bit integers
    If isDeceptive(i) Then
        Print Using "#######"; Csng(i);
        c += 1
        If (c Mod 10) = 0 Then Print
    End If
    i += 1
Wend

Sleep
Output:
Same as XPLo entry.

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

wheel=. 4 6 2 6 4 2 4 2
fermat=. {{1 = 10 (y&|@^) <: y}}"0

_10 ]\ (#~ fermat) (#~ 0&p:) +/\ 49 , 15e4 $ wheel
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
216001 216931 225589 226273 229633 231337 234421 237169 237817 245491
247753 248677 250717 251251 252601 253099 269011 269569 274231 281821
286903 287749 287809 294409 298033 301081 302177 304057 314821 334153
340561 341503 346801 351809 357641 364277 366337 372731 385003 390313
391141 399001 401401 410041 413339 420343 437251 451091 455971 458641
463241 463489 481601 488881 489997 491063 492101 497377 497503 497927
505363 507529 509971 511969 512461 520801 522349 530881 532171 552721

Java

public final class DeceptiveNumbers {

	public static void main(String[] aArgs) {
		int n = 7;
		int count = 0;
		while ( count < 100 ) {
			if ( isDeceptive(n) ) {
				System.out.print(String.format("%6d%s", n, ( ++count % 10 == 0 ? "\n" : " " )));
			}
			n += 1;
		}
	}
	
	private static boolean isDeceptive(int aN) {
		if ( aN % 2 != 0 && aN % 3 != 0 && aN % 5 != 0 && modulusPower(10, aN - 1, aN) == 1 ) {
			for ( int divisor = 7; divisor < Math.sqrt(aN); divisor += 6 ) {
				if ( aN % divisor == 0 || aN % ( divisor + 4 ) == 0 ) {
					return true;
				}
			}
		}
		return false;
	}
	
	private static long modulusPower(long aBase, long aExponent, long aModulus) {
	    if ( aModulus == 1 ) {
	        return 0;
	    }	    
	    
	    aBase %= aModulus;
	    long result = 1;
	    while ( aExponent > 0 ) {
	        if ( ( aExponent  & 1 ) == 1 ) {
	            result = ( result * aBase ) % aModulus;
	        }
	        aBase = ( aBase * aBase ) % aModulus;
	        aExponent >>= 1;
	    }
	    return result;
	}
	
}
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

jq

Adapted from Wren

Works with gojq and fq, the Go implementations of jq

The following program assumes integer arithmetic is sufficiently accurate. Both gojq and fq meet this requirement as they support unbounded precision integer arithmetic.

Execution time using gojq on a 3GHz machine: 0.20s

def is_prime:
  . as $n
  | if ($n < 2)         then false
    elif ($n % 2 == 0)  then $n == 2
    elif ($n % 3 == 0)  then $n == 3
    elif ($n % 5 == 0)  then $n == 5
    elif ($n % 7 == 0)  then $n == 7
    elif ($n % 11 == 0) then $n == 11
    elif ($n % 13 == 0) then $n == 13
    elif ($n % 17 == 0) then $n == 17
    elif ($n % 19 == 0) then $n == 19
    else 23
    | until( (. * .) > $n or ($n % . == 0); .+2)
	| . * . > $n
    end;

# Output: a stream
def deceptives:
  {nextrepunit: 1111111111111111}
  | foreach range(17; infinite; 2) as $n (.;
      .repunit = .nextrepunit
      | .nextrepunit |= . * 100 + 11;
      select( ($n | is_prime | not)
               and ($n % 3 != 0) and ($n % 5 != 0)
               and (.repunit % $n == 0 ))
      | $n );

"The first 25 deceptive numbers are:", [limit(25;deceptives)]
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]

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

langur

Translation of: ALGOL 68
val isPrime = fn(i) {
	i == 2 or i > 2 and
	     not any(series(2 .. i ^/ 2, asconly=true), by=fn x:i div x)
}

var nums = []
var repunit = 111_111

for n = 9; len(nums) < 10; n += 2 {
    repunit = repunit * 100 + 11
    if not isPrime(n) and repunit div n {
        nums = more(nums, n)
    }
}

writeln nums
Output:
[91, 259, 451, 481, 703, 1729, 2821, 2981, 3367, 4141]

LFE

Translation of: Scheme
(defmodule deceptives
   (export (prime? 1) (deceptives 1)))

(defun prime? (n)
   (if (< n 2)
      'false
      (prime? n 2 0 #B(1 2 2 4 2 4 2 4 6 2 6))))

(defun prime? (n d j wheel)
   (cond
      ((=:= j (byte_size wheel))
         (prime? n d 3 wheel))
      ((> (* d d) n)
         'true)
      ((=:= 0 (rem n d))
         'false)
      (else
         (prime? n (+ d (binary:at wheel j)) (+ j 1) wheel))))

(defun deceptives (n)
   (deceptives 2 1 n '()))

(defun deceptives
   ((_ _ 0 l)
      (lists:reverse l))
   ((k r n l)
      (if (andalso (not (prime? k)) (=:= 0 (rem r k)))
         (deceptives (+ k 1) (+ (* r 10) 1) (- n 1) (cons k l))
         (deceptives (+ k 1) (+ (* r 10) 1) n l))))
Output:
lfe> (slurp "deceptive.lfe")
#(ok deceptives)
lfe> (lfe_io:format "~w~n" (list (deceptives 10)))
(91 259 451 481 703 1729 2821 2981 3367 4141)
ok

Lua

Based on the second Wren sample, finds the numbers without needing large integers - see the talk page for more details.

do  -- find deceptive numbers - repunits R(n) evenly divisible by composite numbers and n+1
    -- see tha task talk page based on the second Wren sample

    -- returns true if n is prime, false otherwise, uses trial division          %
    local function isPrime ( n )
        if     n < 3      then return n == 2
        elseif n % 3 == 0 then return n == 3
        elseif n % 2 == 0 then return false
        else
            local prime = true
            local f, f2, toNext = 5, 25, 24
            while f2 <= n and prime do
                prime  = n % f ~= 0
                f      = f + 2
                f2     = toNext
                toNext = toNext + 8
            end
            return prime
        end
    end

    do  -- task
        local n, count = 47, 0
        while count < 25 do
            n = n + 2
            if n % 3 ~= 0 and n % 5 ~= 0 and not isPrime( n ) then
                local mp = 10
                for p = 2, n - 1 do mp = ( mp * 10 ) % n end
                if mp == 1 then
                    count = count + 1
                    io.write( string.format( " %5d", n ) )
                    if count % 10 == 0 then io.write( "\n" ) end
                end
            end
        end
    end

end
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

Mathematica /Wolfram Language

ClearAll[DeceptiveNumberQ]
DeceptiveNumberQ[n_Integer] := If[! PrimeQ[n], PowerMod[10, n - 1, 9 n] == 1]
c = 0;
out = Reap[Do[
     If[DeceptiveNumberQ[i],
      Sow[i];
      c++;
      If[c >= 1000, Break[]]
      ]
     ,
     {i, 2, \[Infinity]}
     ]][[2, 1]];
Print["The first 100:"]
Multicolumn[Take[out, 100], Appearance -> "Horizontal"]
Print["The 1000th is: ", out[[1000]]]
Output:
The first 100:
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

The 1000th is: 24279289

Maxima

/* Function for repunit numbers */
repunit(n):=(10^n-1)/9;

/* Function that checks if property is satisfied */
repunit_property(n):=is(mod(repunit(n-1),n)=0);

/* Function to list the first n deceptive numbers */
deceptive_list(n):=block([deceptives:[],count:0,i:5],
while count<n do (if repunit_property(i) and not primep(i) then (push(i,deceptives),count:count+1),i:i+1),
reverse(deceptives));
Output:
deceptive_list(10);
[91,259,451,481,703,1729,2821,2981,3367,4141]

Nim

Translation of: Python

This algorithm doesn’t need a multiprecision library, but we have to define the modular exponentiation as is is not provided by the standard library.

import std/[math, strutils]

func pow(a, n: Natural; m: Positive): Natural =
  var a = a mod m
  var n = n
  if a > 0:
    result = 1
    while n > 0:
      if (n and 1) != 0:
        result = (result * a) mod m
      n = n shr 1
      a = (a * a) mod m

func sqrt(n: Natural): Natural = Natural(sqrt(float(n)))

func isDeceptive(n: Natural): bool =
  if (n and 1) != 0 and n mod 3 != 0 and n mod 5 != 0 and pow(10, n - 1, n) == 1:
    for d in countup(7, sqrt(n), 6):
      if n mod d == 0 or n mod (d + 4) == 0:
        return true
  result = false

var count = 0
var n = 7
while true:
  if n.isDeceptive:
    inc count
    stdout.write align($n, 6)
    stdout.write if count mod 10 == 0: '\n' else: ' '
    if count == 100: break
  inc 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  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

OCaml

let modpow m =
  let rec loop p b e =
    if e land 1 = 0
    then if e = 0 then p else loop p (b * b mod m) (e lsr 1)
    else loop (p * b mod m) (b * b mod m) (e lsr 1)
  in loop 1

let is_deceptive n =
  let rec loop x =
    x * x <= n && (n mod x = 0 || n mod (x + 4) = 0 || loop (x + 6))
  in
  n land 1 <> 0 && n mod 3 <> 0 && n mod 5 <> 0 &&
  modpow n 10 (pred n) = 1 && loop 7

let () =
  Seq.(ints 49 |> filter is_deceptive |> take 100
  |> iter (Printf.printf " %u%!")) |> print_newline
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

PARI/GP

Rep(n)=sum(X=0,n-1,10^X)
c=0
n=4
while(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,

PascalABC.NET

uses School;

function Deceptives(num: integer): List<integer>;
begin
  Result := new List<integer>;
  var n := 2;
  var r:BigInteger := 1;
  while Result.Count < num do
  begin
    if not n.IsPrime and (r mod n = 0) then
      Result.Add(n);
    n += 1;
    r := 10*r + 1;
  end;
end;

begin
  Deceptives(25).Println;
end.
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

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

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)

without bigints

Somewhat faster, at least until you(or I) up the limits to something silly...

with javascript_semantics
constant limit = iff(platform()=JS?100:1000), showlim=70
atom t0 = time(), t1 = t0+1
integer n = 1, count = 0
printf(1,"The first %d deceptive numbers are:\n",showlim)
while count<limit do
    n += 2
    if gcd(n,3*5)=1 
    and not is_prime(n)
    and powmod(10,n-1,n)=1 then
        count += 1
        if count<=showlim then
            printf(1," %7d%n",{n,remainder(count,10)=0})
        elsif count=limit or time()>t1 then
            printf(1,"The %d%s is %d\r",{count,ord(count),n})
            t1 = time()+1
        end if
    end if
end while
printf(1,"\n%s\n",elapsed(time()-t0))
Output:

As above, plus

The 1000th is 24279289
4 minutes and 59s

or under p2js:

The 100th is 201917
0.4s

Prolog

checkpair(1, 2).
checkpair(R, K) :-
    checkpair(R0, K0),
    R is 10*R0 + 1,
    K is K0 + 1.

deceptive(K) :-
    checkpair(R, K),
    \+ prime(K),
    divmod(R, K, _, 0).

task(K, Ns) :-
    lazy_findall(N, deceptive(N), Ds),
    length(Ns, K),
    prefix(Ns, Ds).

% check if a number is prime
%
wheel235(L) :-
   W = [4, 2, 4, 2, 4, 6, 2, 6 | W],
   L = [1, 2, 2 | W].

prime(N) :-
   N >= 2,
   wheel235(W),
   prime(N, 2, W).

prime(N, D, _) :- D*D > N, !.
prime(N, D, [A|As]) :-
    N mod D =\= 0,
    D2 is D + A, prime(N, D2, As).
Output:
?- task(10, Ns),write(Ns).
[91,259,451,481,703,1729,2821,2981,3367,4141]
Ns = [91, 259, 451, 481, 703, 1729, 2821, 2981, 3367|...].

Python

By using a generic test:
from itertools import count, islice
from math import isqrt

def is_deceptive(n):
    if n & 1 and n % 3 and n % 5 and pow(10, n - 1, n) == 1:
        for d in range(7, isqrt(n) + 1, 6):
            if not (n % d and n % (d + 4)): return True
    return False

print(*islice(filter(is_deceptive, count(49)), 100))
Optimized variant to efficiently generate a sequence:

This uses a wheel to skip the multiples of 2, 3, and 5. The found primes are cached to speedup the full primality test.

from itertools import accumulate, cycle, islice
from math import isqrt

primes = []
wheel = 4, 2, 4, 2, 4, 6, 2, 6

def is_pseudo(n):
    if pow(10, n - 1, n) == 1:
        s = isqrt(n)
        for p in primes:
            if p > s: break
            if n % p == 0: return True
        primes.append(n)
    return False

print(*islice(filter(is_pseudo, accumulate(cycle(wheel), initial=7)), 100))
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

Quackery

isprime is defined at Primality by trial division#Quackery.

  [ 10 swap ** 1 - 9 / ] is rep ( n --> n )

  [] 0
  [ 2 + dup 1+ isprime if again
    dup rep over 1+ mod if again
    tuck 1+ join
    tuck size 20 = until ]
  drop echo
Output:
[ 91 259 451 481 703 1729 2821 2981 3367 4141 4187 5461 6533 6541 6601 7471 7777 8149 8401 8911 ]

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

RPL

Based on the hints given on the Talk page.

Works with: HP version 49
« { } 49
  WHILE OVER SIZE 10 < REPEAT
     IF DUP 3 MOD OVER 5 MOD AND THEN
        IF DUP ISPRIME? NOT THEN
           DUP MODSTO 10 OVER 1 - POWMOD
           IF 1 == THEN SWAP OVER + SWAP END
     END END
     2 +
  END DROP
» 'TASK' STO 

Runs in 4 minutes on a HP-50g.

With a wheel:

« { 4 6 2 6 4 2 4 2 } DUP SIZE → wheel wsize 
  « { } 49
    WHILE OVER SIZE 10 < REPEAT
       1 wsize FOR j
          IF DUP ISPRIME? NOT THEN
             DUP MODSTO 10 OVER 1 - POWMOD
             IF 1 == THEN SWAP OVER + SWAP END
          END
          wheel j GET + 
       NEXT
    END DROP
» » 'TASK' STO  

Runs in 1:26 minutes on a HP-50g.

Output:
1: { 91 259 451 481 703 1729 2821 2981 3367 4141 }

Ruby

require 'prime'

deceptives = Enumerator.new do |y|
  10.step(by: 10) do |n|
    [1,3,7,9].each do |digit|
      cand = n + digit
      next if cand % 3 == 0 || cand.prime? 
      repunit = ("1"*(cand-1)).to_i
      y << cand if (repunit % cand) == 0
    end
  end
end

p deceptives.take(25).to_a
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

Scheme

Uses a Chez Scheme extension for defining a circular list.

(define prime?
   (let ((wheel '(1 2 2 . #1=(4 2 4 2 4 6 2 6 . #1#))))
      (lambda (n)
         (if (< n 2)
            #f
            (let loop ((f 2) (w wheel))
               (cond
                  ((> (* f f) n)  #t)
                  ((zero? (remainder n f))  #f)
                  (#t  (loop (+ f (car w)) (cdr w)))))))))

(define (deceptives n)
   (let loop ((k 2) (r 1) (n n) (l '()))
      (if (zero? n)
         (reverse! l)
         (if (and (not (prime? k)) (zero? (remainder r k)))
            (loop (+ k 1) (+ (* 10 r) 1) (- n 1) (cons k l))
            (loop (+ k 1) (+ (* 10 r) 1) n l)))))
Output:
Chez Scheme Version 9.5
Copyright 1984-2017 Cisco Systems, Inc.

> (deceptives 10)
(91 259 451 481 703 1729 2821 2981 3367 4141)

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

UNIX Shell

Works with POSIX-compatible shells.

is () {
    return "$((!($1)))"
}

fermat_test () {
    set -- 1 "$1" "$(($2 - 1))" "$2"
    while is "$3 > 0"
    do
        set -- "$(($1 * (-($3 & 1) & ($2 ^ 1) ^ 1) % $4))" "$(($2 * $2 % $4))" "$(($3 >> 1))" "$4"
    done
    return "$(($1 != 1))"
}

set -- 7
c=0 n=$1
while :
do
    for w in 4 2 4 2 4 6 2 6
    do
        fermat_test 10 "$((n += w))" && for p
        do
            is 'p * p > n' && {
                set -- "$@" "$n"
                break
            }
            is 'n % p == 0' && {
                echo "$n"
                is '(c += 1) == 10' && exit
                break
            }
        done
    done
done
Output:
91
259
451
481
703
1729
2821
2981
3367
4141

V (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 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)
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]

As discussed in the talk page, it is also possible to do this task without using big integers and the following version runs under Wren-cli albeit somewhat slower at 0.103 seconds for the first 25 deceptive numbers and 0.978 seconds for the first 62. The output is the same as the GMP version.

import "./math" for Int

var count = 0
var limit = 25 // or 62
var n = 49
var deceptive = []
while (count < limit) {
    if (!Int.isPrime(n) && n % 3 != 0 && n % 5 != 0 && Int.modPow(10, n-1, n) == 1) {
        deceptive.add(n)
        count = count + 1
    }
    n = n + 2
}
System.print("The first %(limit) deceptive numbers are:")
System.print(deceptive)

XPL0

Translation of: C
func ModPow(B, E, M);
int  B, E, M, P;
[P:= 1;
while E # 0 do
    [if E & 1 then
        P:= rem(P*B/M);
    B:= rem(B*B/M);
    E:= E >> 1;
    ];
return P;
];

func IsDeceptive(N);
int  N, X;
[if (N&1) # 0 and rem(N/3) # 0 and rem(N/5) # 0 then
    [X:= 7;
    while X*X <= N do
        [if rem(N/X) = 0 or rem(N/(X+4)) = 0 then
            return ModPow(10, N-1, N) = 1;
        X:= X + 6;
        ];
    ];
return false;
];

int C, I;
[Format(7, 0);
I:= 49;  C:= 0;
while C # 41 do \limit for signed 32-bit integers
    [if IsDeceptive(I) then
        [RlOut(0, float(I));
        C:= C+1;
        if rem(C/10) = 0 then CrLf(0);
        ];
    I:= I+1;
    ];
]
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
Cookies help us deliver our services. By using our services, you agree to our use of cookies.