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
 Numbers Aplenty - Deceptive numbers
 OEIS:A000864 - Deceptive nonprimes: composite numbers k that divide the repunit R_{k-1}




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.
 