Using jugs of known capacities to get certain quantity

Suppose you only have a few containers of known capacities for measuring quantities, for example two jugs of 5 and 7 litres of capacity respectively, and you want to use them to obtain exactly 1 litre, for example. Can you do it?

To solve this kind of problems, I wrote a simple Perl program, jugs.pl, that explores the solutions using a brute-force backtracking algorithm limiting its recursivity level for finding the solutions with minimum steps.

There are two versions of these problems, one having a limited quantity of the substance to be moved from one jug to another, and other having an unlimited quantity available to fill any jug and discard it. My program only supports the first version, since the second one can be simulated by creating one jug filled with a large quantity that represents the source and sink of the substance, for example:

This way you can use the program to print a solution for the problem:

$ perl jugs.pl 20,7,5 20,0,0 1
(12) (7) (1)    1->3 3->2 1->3 3->2 2->1 3->2 1->3 3->2
$ perl jugs.pl
Use: perl jugs.pl M1,M2,...,MX I1,I2,...,IX N [NUMSTEPS]
Minimum steps to obtain N units in one of X jugs
given the Maximum and Initial quantity for each jug.

This way you can explore different configurations to learn more from the problem, even setting the number of steps of the solutions. Enjoy!

Simulating a dice of any number of sides by rolling a different dice

Suppose for example that you have a dice of 6 sides and you want to obtain a random result between 1 and 8, how could you do it?

Well, one way is running my Perl script anydice.pl, rolling the dice the indicated number of times and then checking what is the result indicated by the tables printed by the program.

The method used by the program is explained in the paper "Simulating a dice with a dice" by B. Kloeckner.

$ perl anydice.pl
Use: anydice.pl [-d N] [-w] MAX
Print tables to get a random number from 1 to MAX by rolling a dice.
  -d N, -dN    Use a dice of N sides, 6 by default
  -w           Print the tables in HTML instead of ASCII
Important: When rolling a dice many times, if you get the result ?
then you must repeat ALL the rolls to get a correct probability.
$ perl anydice.pl -d6 8
A\B| 1 2 3 4 5 6
---+------------
 1 | 1 1 1 1 2 2
 2 | 2 2 3 3 3 3
 3 | 4 4 4 4 5 5
 4 | 5 5 6 6 6 6
 5 | 7 7 7 7 8 8
 6 | 8 8 ? ? ? ?

In this case, you must roll the D6 two times, A and B, and then look at the table to see what is the result. Note that if you get the result "?" when rolling the dice many times, then you must repeat all the rolls from the beginning, otherwise you will get certain results with a probability not equal to the others.

Cistercian numerals in ASCII Art

So you want to convert any number to the Cistercian numerals in your terminal? Well, in that case please download my cisternum.pl Perl script to do it and enjoy how the monks from the XIII century used to write numbers!

$ perl cisternum.pl
Use: cisternum.pl [-h|-v] NUMBER ...
Converts numbers to Cistercian numerals represented in ASCII.

 NUMBER Number encoded using Arabic numerals from 0 to 9999
 -h     Uses the horizontal representation, the default
 -v     Uses the vertical representation instead of horizontal

$ perl cisternum.pl 2024 07 16
           _         _      
 _\____   |______    ______ 
  |  |              |       

$ perl cisternum.pl -v 2024 07 16
          _    _   
 _|/     | |    | |
  |      |      |  
 _|      |      |  
  |      |      |  

Exploring the paths between two points of a grid

Many results in combinatorics can be generated counting all the different ways to make something in the real world. As an example, consider the lines connecting points in a grid or lattice:

o-------o   .   .
        |
.   .   o---o   .
            |
.   .   .   |   .
            |
.   .   .   o---o
                |
.   .   .   .   o

This figure can be associated to many objects in the real world, like a walk through the streets of a city or multiple movements of a chess rook. The number of different paths like this in a grid of NxN points using only two directions to move and not crossing the main diagonal of the grid is equal to the Catalan number N, and these paths are also known as Dyck paths. Interestingly, including the moves crossing the main diagonal generates exactly the numbers of the famous Pascal's triangle, that is, the Binomial coeficients.

OK, but, what happens if we use a chess queen instead?

Thinking in that question I wrote a program to print these paths, and I generalized it to optionally include moves surpassing the main diagonal of the grid and to optionally include diagonal paths. I published the result in LatticePath and it prints the paths in ASCII:

> java -jar LatticePath.jar --pass --diag 5
...
o---o---o
        |
        o---o
            |
            o
            |
            o
            |
            o---o

o---o---o
        |
        o
         '.
           'o---o
                |
                o
                |
                o

o---o---o
        |
        o
         '.
           'o
             '.
               'o
                |
                o
...
> java -jar LatticePath.jar --pass --diag --count 5
1	1	1	1	1
1	3	5	7	9
1	5	13	25	41
1	7	25	63	129
1	9	41	129	321

After writing the first version of the program I realized that including diagonal moves generates different kinds of numbers: The number of paths not surpassing the main diagonal of the grid is called Schröder number, and the number of paths surpassing the main diagonal of the grid is called Delannoy number. How many connections from only a few simple rules! Thanks also to the OEIS site for being so useful for knowing the name of any sequence of numbers.

I hope you enjoy the program LatticePath and the minimalistic style in which it is programmed!

Why the area of a square of side L is LxL?

Recently I watched a video talking about the difference of the volume of the sphere of radius 1 and the cube of side 1 in N-dimensions, and I asked myself why the cube volume is always 1 in any dimension, or, which is an equivalent question:

Why the area of a square of side L is LxL?

Because the unit to measure areas is the square of side 1.

Why the unit to measure areas is the square of side 1?

Because it's convenient, since we usually measure areas by dividing them in rectangles and then measuring the sides of those rectangles. But it's not mandatory!

What happens if we change the unit to measure areas?

Well, you can continue doing maths, but then, the area formulas will be all wrong. Yes, they only work if you first state that the area of a square of side 1 is 1. Anyway, the resulting formulas will only be different by a multiplying constant.

It's an interesting exercise to derivate the main area formulas by choosing, for example, the equilateral triangle of side 1 as the area unit if you like square roots and Pythagoras, or the circle of radius 1 as the area unit if you like π and how to measure circles with triangles and vice versa.

As with the common use of our arbitrary base 10, it's important to note that much of our mathematical knowledge, as the formula of the area of the rectangle, is just conventional. Think about it before talking to any aliens, or perhaps you will not be able to understand each other...

Generate in Perl all the Dyck words of length 2N

 The Dyck words are the elements that form the Dyck language and can be defined as any sequence of parenthesis correctly balanced, for example, these are the Dyck words having 3 pairs of parenthesis:

((()))  (()())  (())()  ()(())  ()()()

Also, the number of Dyck words of length 2N is equal to the Nth Catalan number, registered in OEIS as A000108, and the Dyck words can be converted to many geometric representations of the Catalan numbers.

The following program in Perl generates all the Dyck words of length 2N using the characters "0" and "1", receiving N as argument:

#!/usr/bin/perl
# dyck.pl - prints all dyck words of length 2N given N as argument
my $s=('0'x$ARGV[0]).('1'x$ARGV[0]); my $t;
do{
    print $s, "\n";
}while($s=~s/(.*)01(1.*)/$1.'10'.join('',($t=$2)=~m'0'g).join('',$t=~m'1'g)/e);

On each iteration, the last instruction generates the next word transforming the current word by finding the last "011", replacing "01" with "10" and then reordering the other "1" and its following characters (if any) placing first the 0's and then the 1's.

Code explanation: The variables $1 and $2 store the begining and the end of the word found by the regular expression (.*)01(1.*) and the variable $t is used to save the content of $2 because $1 and $2 are rewritten when the other regular expression operators =~ are executed for collect and separate the 0's and the 1's of the end.

For example:

> perl dyck.pl 4
00001111
00010111
00011011
00011101
00100111
00101011
00101101
00110011
00110101
01000111
01001011
01001101
01010011
01010101

Enjoy it!

Generate in Perl the numbers with digits in order

If you try to count using only numbers with all its digits in ascending order, you will get this:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 22, 23, 24, 25, 26, 27, 28, 29, 33, 34, 35, 36, 37, 38, 39, 44, 45, 46, 47, 48, 49, 55, 56, 57, 58, 59, 66, 67, 68, 69, 77, 78, 79, 88, 89, 99, 111, 112, 113, 114, 115, 116, 117, 118, 119, 122, 123, ...

This sequence is registered in OEIS as A009994 - Numbers with digits in nondecreasing order.

Note that all the jumps are located after the last digit becomes 9, because the digit 0 cannot appear after the first occurrence. Considering this, I have created a little Perl program to generate it:

#!/usr/bin/perl
for($_="";;) {
    s/([0-8]?)(9*)$/$2?($1?$1+1:1)x(length($2)+1):length($1)?$1+1:0/e;
    print "$_\n";
}

On each iteration, the regular expression is applied to the variable $_ generating the next number, following this algorithm:

• If there are one or more 9's at the end then:
• If there is a digit X<9 just before the 9's then that digit X and those 9's are all replaced with the digit X+1 repeated as many times as the number of 9's plus one, for example 22499=>22555
• If there is no digit just before the 9's then is considered that the digit is 0 and the same operation is done, for example 999=>1111
• If there are no 9's at the end then:
• If there is a digit X at the end then the digit X is replaced with the digit X+1, for example 133=>134
• If there is no digit in the number then the digit 0 is inserted

I tried to do the code as easy to understand as I could, so you can use it if you need without problem ;-). Thanks for reading!

Program to find the maximum multiplicative persistence

After watching an interesting video from Numberphile about multiplicative persistence, one of the basic operations in Persistence of numbers, I thought that I wanted to make it by myself in Perl, so here you have the program multdigits.pl:

$ perl multdigits.pl -h

Usage: perl multdigits.pl [OPTION]...
Multiply the digits of each integer recursively until get one digit,
printing all the products obtained and counting the number of them.
See https://oeis.org/A003001 for more information about the sequence.

-r, --radix=NUM   use the NUM radix or base, 10 by default
-s, --sorted      use only numbers with sorted digits as optimization
-m, --mindigit=N  when sorted, minimum digit to optimize, 1 by default
-a, --all         prints all instead of only those with more products
-o, --others      prints others with same product number, not 1st only
-d, --dots        print dots when reaches a number with one digit more
-i, --initial=NUM initial number to begin the search, 0 by default
-h, --help        print the help and exits

Faster options: perl multdigits.pl --sorted --mindigit=2 --indicator
Copyright 2021 Carlos Rica <jasampler AT gmail DOT com>

Using the faster options it finds pretty fast the smallest integer (277777788888899) having the maximum multiplicative persistence known (11) for base 10, and then the program cannot reach numbers much bigger than that, but it can do it in any base, and also it can show other numbers with the same maximum multiplicative persistence, which give interesting information about the repetition of the longest sequences of products. Enjoy!

Magic squares generator in C

2021-11-10: NOTE: I rewrote the program to make it faster in magic-square.

A magic square is a table with equal number of rows and columns that is filled with all the numbers from 1 to NxN (being N the number of rows) in a way that verifies that the sum of the numbers in any row, in any column and in any of the two diagonals gives the same result in all cases, which is called the magic constant. If you choose a different initial number than 1 for filling the square (even zero or negative) and a different increment than 1 to get the following numbers, you will also get the same number of magic squares although the magic constant will change.

Because by rotation or reflection of a magic square you can get other 8 magic squares, only one of those variations (or trivial solutions) is counted. One magic square of size 1x1 exists, zero magic squares of size 2x2 exist and one magic square of size 3x3 exist (with 8 rotations and/or reflections) whose lines sum 15. If you choose the magic square of size 3x3 with the minimum corners, you get this one (printed by my magic square generator):

 2 | 9 | 4 
---+---+---
 7 | 5 | 3 
---+---+---
 6 | 1 | 8 

Exist 880 magic squares of size 4x4 (7040 if you count the trivial solutions) with sum 34, and the magic squares of size 5x5 with sum 65 are many many more, so I created this magic square generator to count them and verify the number of magic squares that others found. Because that number is so big and the program cannot generate all magic squares in a short time, you can can restart the counting from any point by choosing the numbers of the corners with the -c option, although it only accepts ordered numbers for the initial corners. The minimum corners that I have found that generate solutions is this:

$ ./magic-square -c1,2,5,22 5
  1 | 18 | 20 | 24 |  2 
----+----+----+----+----
 23 |  8 |  6 | 12 | 16 
----+----+----+----+----
 19 |  3 | 25 |  7 | 11 
----+----+----+----+----
 17 | 21 |  4 |  9 | 14 
----+----+----+----+----
  5 | 15 | 10 | 13 | 22 
...

To stop the program you can hit Control+C or wait until it reaches the last corners 22,23,24,25. The available options are shown by executing the program without arguments. The -q option counts the solutions without printing them. Happy searching!