Brazilian numbers are so called as they were first formally presented at the 1994 math Olympiad Olimpiada Iberoamericana de Matematica in Fortaleza, Brazil.

Brazilian numbers are defined as:

The set of positive integer numbers where each number N has at least one natural number B where 1 < B < N-1 where the representation of N in base B has all equal digits.



E.G.

 1, 2 & 3 can not be Brazilian; there is no base B that satisfies the condition 1 < B < N-1.
 4 is not Brazilian; 4 in base 2 is 100. The digits are not all the same.
 5 is not Brazilian; 5 in base 2 is 101, in base 3 is 12. There is no representation where the digits are the same.
 6 is not Brazilian; 6 in base 2 is 110, in base 3 is 20, in base 4 is 12. There is no representation where the digits are the same.
 7 is Brazilian; 7 in base 2 is 111. There is at least one representation where the digits are all the same.
 8 is Brazilian; 8 in base 3 is 22. There is at least one representation where the digits are all the same.
 and so on...


All even integers 2P >= 8 are Brazilian because 2P = 2(P-1) + 2, which is 22 in base P-1 when P-1 > 2. That becomes true when P >= 4.

More common: for all all integers R and S, where R > 1 and also S-1 > R, then R*S is Brazilian because R*S = R(S-1) + R, which is RR in base S-1

The only problematic numbers are squares of primes, where R = S. Only 11^2 is brazilian to base 3.

All prime integers, that are brazilian, can only have the digit 1. Otherwise one could factor out the digit, therefore it cannot be a prime number. Mostly in form of 111 to base Integer(sqrt(prime number)). Must be an odd count of 1 to stay odd like primes > 2


Task

Write a routine (function, whatever) to determine if a number is Brazilian and use the routine to show here, on this page;

 the first 20 Brazilian numbers;
 the first 20 odd Brazilian numbers;
 the first 20 prime Brazilian numbers;


See also

 OEIS:A125134 - Brazilian numbers
 OEIS:A257521 - Odd Brazilian numbers
 OEIS:A085104 - Prime Brazilian numbers


program brazilianNumbers;
 
{$IFDEF FPC}
  {$MODE DELPHI}{$OPTIMIZATION ON,All}
  {$CODEALIGN proc=32,loop=4}
{$ELSE}
  {$APPTYPE CONSOLE}
{$ENDIF}
uses
  SysUtils;
 
const
  //Must not be a prime
  PrimeMarker = 0;
  SquareMarker = PrimeMarker + 1;
  //MAX =    110468;// 1E5 brazilian
  //MAX =   1084566;// 1E6 brazilian
  //MAX =  10708453;// 1E7 brazilian
  //MAX = 106091516;// 1E8 brazilian
  MAX = 1053421821;// 1E9 brazilian
 
var
  isprime: array of word;
 
  procedure MarkSmallestFactor;
  //sieve of erathotenes
  //but saving the smallest factor
  var
    i, j, lmt: NativeUint;
  begin
    lmt := High(isPrime);
    fillWord(isPrime[0], lmt + 1, PrimeMarker);
    //mark even numbers
    i := 2;
    j := i * i;
    isPrime[j] := SquareMarker;
    Inc(j, 2);
    while j <= lmt do
    begin
      isPrime[j] := 2;
      Inc(j, 2);
    end;
    //mark 3 but not 2
    i := 3;
    j := i * i;
    isPrime[j] := SquareMarker;
    Inc(j, 6);
    while j <= lmt do
    begin
      isPrime[j] := 3;
      Inc(j, 6);
    end;
 
    i := 5;
    while i * i <= lmt do
    begin
      if isPrime[i] = 0 then
      begin
        j := lmt div i;
        if not (odd(j)) then
          Dec(j);
        while j > i do
        begin
          if isPrime[j] = 0 then
            isPrime[i * j] := i;
          Dec(j, 2);
        end;
        //mark square prime
        isPrime[i * i] := SquareMarker;
      end;
      Inc(i, 2);
    end;
  end;
 
  procedure OutFactors(n: NativeUint);
  var
    divisor, Next, rest: NativeUint;
    pot: NativeUint;
  begin
    divisor := 2;
    Next := 3;
    rest := n;
    Write(n: 10, ' = ');
    while (rest <> 1) do
    begin
      if (rest mod divisor = 0) then
      begin
        Write(divisor);
        pot := 0;
        repeat
          rest := rest div divisor;
          Inc(pot)
        until rest mod divisor <> 0;
        if pot > 1 then
          Write('^', pot);
        if rest > 1 then
          Write('*');
      end;
      divisor := Next;
      Next := Next + 2;
      // cut condition: avoid many useless iterations
      if (rest <> 1) and (rest < divisor * divisor) then
      begin
        Write(rest);
        rest := 1;
      end;
    end;
    Write('  ', #9#9#9);
  end;
 
  procedure OutToBase(number, base: NativeUint);
  var
    BaseDgt: array[0..63] of NativeUint;
    i, rest: NativeINt;
  begin
    OutFactors(number);
    i := 0;
    while number <> 0 do
    begin
      rest := number div base;
      BaseDgt[i] := number - rest * base;
      number := rest;
      Inc(i);
    end;
    while i > 1 do
    begin
      Dec(i);
      Write(BaseDgt[i]);
    end;
    writeln(BaseDgt[0], ' to base ', base);
  end;
 
  function PrimeBase(number: NativeUint): NativeUint;
  var
    lnN: extended;
    i, exponent, n: NativeUint;
  begin
    // primes are only brazilian if 111...11 to base > 2
    // the count of "1" must be odd , because brazilian primes are odd
    lnN := ln(number);
    exponent := 4;
    //result := exponent.th root of number
    Result := trunc(exp(lnN*0.25));
    while result >2 do
    Begin
      // calc sum(i= 0 to exponent ) base^i;
      n := Result + 1;
      i := 2;
      repeat
        Inc(i);
        n := n*result + 1;
      until i > exponent;
      if n = number then
        EXIT;
      Inc(exponent,2);
      Result := trunc(exp(lnN/exponent));
    end;
    //not brazilian
    Result := 0;
  end;
 
  function GetPrimeBrazilianBase(number: NativeUint): NativeUint;
    //result is base
  begin
    // prime of 2^n - 1
    if (Number and (number + 1)) = 0 then
      Result := 2
    else
    begin
      Result := trunc(sqrt(number));
      //most of the brazilian primes are of this type base^2+base+1
      IF (sqr(result)+result+1) <> number then
        result := PrimeBase(number);
    end;
  end;
 
  function GetBrazilianBase(number: NativeUInt): NativeUint; inline;
  begin
    Result := isPrime[number];
    if Result > SquareMarker then
      Result := (number div Result) - 1
    else
    begin
      if Result = SquareMarker then
      begin
        if number = 121 then
          Result := 3
        else
          Result := 0;
      end
      else
        Result := GetPrimeBrazilianBase(number);
    end;
  end;
 
  procedure First20Brazilian;
  var
    i, n, cnt: NativeUInt;
  begin
    writeln('first 20 brazilian numbers');
    i := 7;
    cnt := 0;
    while cnt < 20 do
    begin
      n := GetBrazilianBase(i);
      if n <> 0 then
      begin
        Inc(cnt);
        OutToBase(i, n);
      end;
      Inc(i);
    end;
    writeln;
  end;
 
  procedure First33OddBrazilian;
  var
    i, n, cnt: NativeUInt;
  begin
    writeln('first 33 odd brazilian numbers');
    i := 7;
    cnt := 0;
    while cnt < 33 do
    begin
      n := GetBrazilianBase(i);
      if N <> 0 then
      begin
        Inc(cnt);
        OutToBase(i, n);
      end;
      Inc(i, 2);
    end;
    writeln;
  end;
 
  procedure First20BrazilianPrimes;
  var
    i, n, cnt: NativeUInt;
  begin
    writeln('first 20 brazilian prime numbers');
    i := 7;
    cnt := 0;
    while cnt < 20 do
    begin
      IF isPrime[i] = PrimeMarker then
      Begin
        n := GetBrazilianBase(i);
        if n <> 0 then
        begin
          Inc(cnt);
          OutToBase(i, n);
        end;
      end;
      Inc(i);
    end;
    writeln;
  end;
 
var
  T1, T0: TDateTime;
  i, n, cnt, lmt: NativeUInt;
begin
  lmt := MAX;
  setlength(isPrime, lmt + 1);
  MarkSmallestFactor;
 
  First20Brazilian;
  First33OddBrazilian;
  First20BrazilianPrimes;
 
  Write('count brazilian numbers up to ', lmt, ' = ');
  T0 := now;
  i := 7;
  cnt := 0;
  n := 0;
 
  while (i <= lmt) do
  begin
    Inc(n, Ord(isPrime[i] = PrimeMarker));
    if GetBrazilianBase(i) <> 0 then
      Inc(cnt);
    Inc(i);
  end;
 
  T1 := now;
 
  writeln(cnt);
  writeln('Count of primes ', n: 11+13);
  writeln((T1 - T0) * 86400 * 1000: 10: 0, ' ms');
 
  setlength(isPrime, 0);
end.