Month: March 2022

Wherein there’s one thing I’m certain of —
Return, I will, to old Brazil…

THE WEEKLY CHALLENGE – PERL & RAKU #157 Task 2

---

“For now I stand as one upon a rock
Environed with a wilderness of sea,
Who marks the waxing tide grow wave by wave,
Expecting ever when some envious surge
Will in his brinish bowels swallow him.”

— William Shakespeare, Titus Andronicus

---

Brazilian Number

Submitted by: Mohammad S Anwar

You are given a number $n > 3.

Write a script to find out if the given number is a Brazilian Number.

A positive integer number N has at least one natural number B where 1 < B < N-1 where the representation of N in base B has same digits.

Example 1:

Input: $n = 7
Output: 1

Since 7 in base 2 is 111.

Example 2:

Input: $n = 6
Output: 0

Since 6 in base 2 is 110,
      6 in base 3 is 20 and
      6 in base 4 is 12.

Example 3:

Input: $n = 8
Output: 1

Since 8 in base 3 is 22.

ANALYSIS

In 1994, at the  9th Iberoamerican Mathematical Olympiad in Fortaleza, Brazil, a problem was posed, prefaced by the following novel definition:

A number n > 0 is called “Brazilian” if there exists an integer b such that 1 <  b < n – 1 for which the representation of n in base b is written with all equal digits

This form, of a number composed of a number of repetitions of a single digit in a given base representation, was not the novel part, having been studied at various time for a few decades at that point. These numbers are called repdigits, or monodigits.

The coinage here was not tying the representation to a single base; rather that it could be done in some base.

Well, almost any. As it turns out any number n is a repdigit when represented in a base one smaller than its value, n-1. Although perhaps not obvious, the reasoning behind this is the same as the possibly more-familiar decimal expansion of ninths: 10/9 = 1.111(1), which is to say an infinite list of 1s. When we divide 10 by the value one less — 9 — then we get 1 with a reptend of 1, and if we write 10 in base-9, we get 11, a repdigit. The infinitely-repeating reptend of a decimal expansion and repdigits are as might be expected closely related concepts.

As such we allow any base but the one one-less than the value. And allowing unary would be silly, as every number in a single-digit number scheme is a repdigit.

METHOD

To find our repdigit base, we’ll need to convert between bases, but unless we want to limit ourselves to small values we won’t have enough characters to actually represent those bases. It’s a predicament. Often base conversion is restricted to an upper bound of base-36 as that’s as high as we can go appending the English alphabet to the digits 0 through 9.

Fortunately we don’t need to actually represent anything, as we don’t need digits specifically, what we really need in the sequence number of the digits, to see that they’re all the same. The sequence number can be in any base, like for instance decimal.

Further we don’t need to actually finish most of the base conversions either. If we remember the first digit, then when computing the next and those following, we only need to notice if it isn’t the same as the first. If it isn’t, we can move on to the next base.

To do the base conversion we perform integer division, dividing down the number and recording the remainder to the operation. The first remainder sets the target for the ones following, and if any don’t match we can immediately short-circuit out of the subroutine.

PERL 5 SOLUTION

my $input = shift @ARGV // 1993;
say "input:  $input";
say "output: ", brazilian( $input ) ? 1 : 0;
 
sub brazilian ( $num ) {
## up/down check if number is a Brazilian number
    for ( 2..$num-2 ) {
        return $_ if digit_test( $num, $_ );
    }
    return 0;
}

sub digit_test ( $num, $base ) {
## up/down check for all digits are the same in a given base 
## converts from base-10 to any given base
## does not internally store converted number other than 
## each digit as base-10 sequence index: conditional 
## 1 short-circuits returning 0 if non-repeated digit found, 
## otherwise returns 1
    my $rem; 
    my $digit;
    while ( $num > 0  ) {
        ($num, $rem) = (int( $num/$base ), $num % $base);   
        $digit //= $rem;
        return 0 if $digit != $rem;
    }
    return 1;
}

Raku Solution

unit sub MAIN ( $num = 1994 ) ;

brazilian( $num ).say;

sub brazilian ( $num ) {
## up/down check if number is a Brazilian number
    return 1 if digit_test( $num, $_ ) for 2..$num-2 ;
    return 0;
}

sub digit_test ( $num is copy, $base ) {
## up/down check for all digits are the same in a given base 
    my $rem; 
    my $digit;
    while ( $num > 0  ) {
        ($num, $rem) = $num div $base, $num % $base;   
        $digit //= $rem;
        return 0 if $digit != $rem;
    }
    return 1;
}