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


begin % find some Brazilian numbers - numbers N whose representation in some %
      % base B ( 1 < B < N-1 ) has all the same digits                       %
    % set b( 1 :: n ) to a sieve of Brazilian numbers where b( i ) is true   %
    % if i is Brazilian and false otherwise - n must be at least 8           %
    procedure BrazilianSieve ( logical array b ( * ) ; integer value n ) ;
    begin
        logical isEven;
        % start with even numbers flagged as Brazilian and odd numbers as    %
        % non-Brazilian                                              %
        isEven := false;
        for i := 1 until n do begin
            b( i ) := isEven;
            isEven := not isEven
        end for_i ;
        % numbers below 7 are not Brazilian (see task notes)                 %
        for i := 1 until 6 do b( i ) := false;
        % flag all 33, 55, etc. numbers in each base as Brazilian            %
        % No Brazilian number can have a representation of 11 in any base B  %
        %    as that would mean B + 1 = N, which contradicts B < N - 1       %
        % also, no need to consider even digits as we know even numbers > 6  %
        %    are all Brazilian                                               %
        for base := 2 until n div 2 do begin
            integer b11, bnn;
            b11 := base + 1;
            bnn := b11;
            for digit := 3 step 2 until base - 1 do begin
                bnn := bnn + b11 + b11;
                if bnn <= n
                then b( bnn ) := true
                else goto end_for_digits
            end for_digits ;
end_for_digits:
        end for_base ;
        % handle 111, 1111, 11111, ..., 333, 3333, ..., etc.                 %
        for base := 2 until truncate( sqrt( n ) ) do begin
            integer powerMax;
            powerMax := MAXINTEGER div base;              % avoid 32 bit     %
            if powerMax > n then powerMax := n;           % integer overflow %
            for digit := 1 step 2 until base - 1 do begin
                integer bPower, bN;
                bPower := base * base;
                bN     := digit * ( bPower + base + 1 ); % ddd               %
                while bN <= n and bPower <= powerMax do begin
                    if bN <= n then begin
                        b( bN ) := true
                    end if_bN_le_n ;
                    bPower := bPower * base;
                    bN     := bN + ( digit * bPower )
                end while_bStart_le_n
            end for_digit
        end for_base ;
    end BrazilianSieve ;
    % sets p( 1 :: n ) to a sieve of primes up to n                          %
    procedure Eratosthenes ( logical array p( * ) ; integer value n ) ;
    begin
        p( 1 ) := false; p( 2 ) := true;
        for i := 3 step 2 until n do p( i ) := true;
        for i := 4 step 2 until n do p( i ) := false;
        for i := 2 until truncate( sqrt( n ) ) do begin
            integer ii; ii := i + i;
            if p( i ) then for pr := i * i step ii until n do p( pr ) := false
        end for_i ;
    end Eratosthenes ;
 
    integer MAX_NUMBER;
    MAX_NUMBER := 2000000;
    begin
        logical array b ( 1 :: MAX_NUMBER );
        logical array p ( 1 :: MAX_NUMBER );
        integer bCount;
        BrazilianSieve( b, MAX_NUMBER );
        write( "The first 20 Brazilian numbers:" );write();
        bCount := 0;
        for bPos := 1 until MAX_NUMBER do begin
            if b( bPos ) then begin
                bCount := bCount + 1;
                writeon( i_w := 1, s_w := 0, " ", bPos );
                if bCount >= 20 then goto end_first_20
            end if_b_bPos
        end for_bPos ;
end_first_20:
        write();write( "The first 20 odd Brazilian numbers:" );write();
        bCount := 0;
        for bPos := 1 step 2 until MAX_NUMBER do begin
            if b( bPos ) then begin
                bCount := bCount + 1;
                writeon( i_w := 1, s_w := 0, " ", bPos );
                if bCount >= 20 then goto end_first_20_odd
            end if_b_bPos
        end for_bPos ;
end_first_20_odd:
        write();write( "The first 20 prime Brazilian numbers:" );write();
        Eratosthenes( p, MAX_NUMBER );
        bCount := 0;
        for bPos := 1 until MAX_NUMBER do begin
            if b( bPos ) and p( bPos ) then begin
                bCount := bCount + 1;
                writeon( i_w := 1, s_w := 0, " ", bPos );
                if bCount >= 20 then goto end_first_20_prime
            end if_b_bPos
        end for_bPos ;
end_first_20_prime:
        write();write( "Various Brazilian numbers:" );
        bCount := 0;
        for bPos := 1 until MAX_NUMBER do begin
            if b( bPos ) then begin
                bCount := bCount + 1;
                if   bCount  =     100
                or   bCount  =    1000
                or   bCount  =   10000
                or   bCount  =  100000
                or   bCount  = 1000000
                then write( s_w := 0, bCount, "th Brazilian number: ", bPos );
                if   bCount >= 1000000 then goto end_1000000
            end if_b_bPos
        end for_bPos ;
end_1000000:
    end
end.