The Bear's Den

Enter at your own risk

Reversible Permutations

Task 1: Permuted Multiples

Submitted by: Mohammad S Anwar


Write a script to find the smallest positive integer x such that x, 2x, 3x, 4x, 5x and 6x are permuted multiples of each other.

For example, the integers 125874 and 251748 are permutated multiples of each other as

251784 = 2 x 125874

and also both have the same digits but in different order.

Output

142857

Solution

Perl

This is a reproduction of my solution dated 6 Aug 2022.


Additional assumptions:

All results for bases 8, 10, 12 and 13 can be found. There are no results for other bases below 13. While base 12 can be handled in about 12 min here, base 13 takes about 5 h.

There is an interesting results in base 8: 1234567

For bases up to 12, the leading digit must always be 1. See below for different results in bases 17, 19 and 24.

use strict;
use warnings;
use Math::Prime::Util qw(fromdigits todigits todigitstring);
use List::Util qw(all);
use Algorithm::Combinatorics qw(variations);
use Coro::Generator;

# Build a generator for "permuted multiples" in the given base.
sub gen_perm_mult ($base) {
    my $done;
    generator {
        # Do not allow the generator to start over.
        yield(undef), return if $done++;
        # The minimum length of such a number cannot be less than six as
        # the number itself and its multiples all have different leading
        # digits if they are of the same length.  The maximum length is
        # the base because all digits shall be distinct.  The
        # $len variable is off by one here as we treat the leading digit
        # separately.
        for my $len (5 .. $base - 1) {
            # There shall be no leading zero and the sixfold of it needs
            # to be below the base.
            for my $ld (1 .. int(($base - 1) / 6)) {
                # Create a hash with all possible digits as keys.
                (\my %digits)->@{0 .. $base - 1} = ();
                # Remove the leading digit.
                delete $digits{$ld};
                # Loop over all variations (a.k.a. k-permutations of n)
                # of digits (except the leading digit) in the given base
                # and in the current length as candidate numbers.
                my $v_it = variations([sort {$a <=> $b} keys %digits], $len);
                while (my $v = $v_it->next()) {
                    # Prepend the leading digit.
                    my @p = ($ld, @$v);
                    # Get the candidate number from the digits in the
                    # given base.
                    my $n = fromdigits \@p, $base;
                    # Check if the digits of all requested multiples of
                    # the candidate number form a permutation of the
                    # candidate number's digits.
                    yield $n
                        if all {isperm(\@p, [todigits $n * $_, $base])} 2..6;
                }
            }
        }
    }
}

# Check if the array @$q is a permutation of @$p.  This is the case if
# all elements of @$p occur in @$q and both arrays have the same length.
sub isperm ($p, $q) {
    return unless @$p == @$q;
    # Create a hash %q having keys from @$q and values 1.
    (\my %q)->@{@$q} = (1) x @$q;
    # Check if all elements of @$p occur in %q.
    @$p == grep $_, @q{@$p};
}

See the full solution to task 1.

Task 2: Reversible Numbers

Submitted by: Mohammad S Anwar


Write a script to find out all Reversible Numbers below 100.

A number is said to be a reversible if sum of the number and its reverse had only odd digits.

For example,

36 is reversible number as 36 + 63 = 99 i.e. all digits are odd.
17 is not reversible as 17 + 71 = 88, none of the digits are odd.

Output

10, 12, 14, 16, 18, 21, 23, 25, 27,
30, 32, 34, 36, 41, 43, 45, 50, 52,
54, 61, 63, 70, 72, 81, 90

Solution

The check for a reversible number is straightforward.

Perl

use strict;
use warnings;
use experimental 'signatures';
use List::Util 'product';

sub reversible_number ($n) {
    product map $_ % 2, split //, $n + reverse $n;
}

See the full solution to task 2.

J

A J noun is either numeric or character. Character operations, e.g. reversing digits, have to be applied to character data. Therefore the number has to be converted from integer to character and back.

NB. check if y is a reversible number
reversible_number =: _(adverb define)
  NB. convert y to decimal digits
  to_digits =. 10&#.inv
  NB. reverse the digits
  reverse =. |.
  NB. Use "u under v" to perform "(v inv) u v y"
  under =. &.
  NB. check if y is odd
  odd =. 2&#:
  NB. "and" over all items of y
  all =. *./
  NB. Add y and its reverse, check if all digits are odd
  ([: all @: odd @ to_digits ] + reverse under to_digits) f. : [:
)

See the full solution.