How to resolve the algorithm Minimum positive multiple in base 10 using only 0 and 1 step by step in the Raku programming language

Published on 12 May 2024 09:40 PM
#Raku

How to resolve the algorithm Minimum positive multiple in base 10 using only 0 and 1 step by step in the Raku programming language

Table of Contents

Problem Statement

Every positive integer has infinitely many base-10 multiples that only use the digits 0 and 1. The goal of this task is to find and display the minimum multiple that has this property. This is simple to do, but can be challenging to do efficiently. To avoid repeating long, unwieldy phrases, the operation "minimum positive multiple of a positive integer n in base 10 that only uses the digits 0 and 1" will hereafter be referred to as "B10". Write a routine to find the B10 of a given integer.
E.G. and so on. Use the routine to find and display here, on this page, the B10 value for: Optionally find B10 for: Stretch goal; find B10 for: There are many opportunities for optimizations, but avoid using magic numbers as much as possible. If you do use magic numbers, explain briefly why and what they do for your implementation.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Minimum positive multiple in base 10 using only 0 and 1 step by step in the Raku programming language

Source code in the raku programming language

say $_ , ': ', (1..*).map( *.base(2) ).first: * %% $_ for flat 1..10, 95..105; # etc.


sub Ed-Pegg-jr (\n) {
    return 1 if n == 1;
    my ($count, $power-mod-n) = 0, 1;
    my @oom-mod-n = 0; # orders of magnitude of 10 mod n
    my @dig-mod = 0;   # 1 to n + oom mod n
    for 1..n -> \i {
        @oom-mod-n[i] = $power-mod-n;
        for 1..n -> \j {
            my \k = (j + $power-mod-n - 1) % n + 1;
            @dig-mod[k] = i if @dig-mod[j] and @dig-mod[j] != i and !@dig-mod[k];
        }
        @dig-mod[$power-mod-n + 1] ||= i;
        ($power-mod-n *= 10) %= n;
        last if @dig-mod[1];
    }
    my ($b10, $remainder) = '', n;
    while $remainder {
        my $place = @dig-mod[$remainder % n + 1];
        $b10 ~= '0' x ($count - $place) if $count > $place;
        $count = $place - 1;
        $b10 ~= '1';
        $remainder = (n + $remainder - @oom-mod-n[$place]) % n;
    }
    $b10 ~ '0' x $count
}

printf "%5s: %28s  %s\n", 'Number', 'B10', 'Multiplier';

for flat 1..10, 95..105, 297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878 {
    printf "%6d: %28s  %s\n", $_, my $a = Ed-Pegg-jr($_), $a / $_;
}

You may also check:How to resolve the algorithm AKS test for primes step by step in the Julia programming language
You may also check:How to resolve the algorithm Sum multiples of 3 and 5 step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm The Twelve Days of Christmas step by step in the Java programming language
You may also check:How to resolve the algorithm Draw a rotating cube step by step in the Nim programming language
You may also check:How to resolve the algorithm Count in octal step by step in the Futhark programming language