Skip to main content
added 1253 characters in body
Source Link
Jaap Scherphuis
  • 55.7k
  • 8
  • 130
  • 221

For those interested, here is the simple C# program I wrote:

  using System;
  using System.Collections.Generic;
  using System.Numerics;

  namespace TempProg
  {
     class PSEsaturday
     {
        public static void Main()
        {
           List<BigInteger> current = new List<BigInteger>();
           List<BigInteger> next = new List<BigInteger>();

           for (int i = 1; i <= 9; i++)
              current.Add(new BigInteger(i));

           int length = 1;
           while(current.Count > 0)
           {
              length++;
              foreach (var n in current)
              {
                 for( int d=0; d<=9; d++)
                 {
                    var n2 = n * 10 + d;
                    if(n2 % length == 0)
                    {
                       next.Add(n2);
                       Console.WriteLine(n2);
                    }
                 }
              }
              var t = current;
              current = next;
              next = t;
              next.Clear();
           }
        }
     }
  }

For those interested, here is the simple C# program I wrote:

  using System;
  using System.Collections.Generic;
  using System.Numerics;

  namespace TempProg
  {
     class PSEsaturday
     {
        public static void Main()
        {
           List<BigInteger> current = new List<BigInteger>();
           List<BigInteger> next = new List<BigInteger>();

           for (int i = 1; i <= 9; i++)
              current.Add(new BigInteger(i));

           int length = 1;
           while(current.Count > 0)
           {
              length++;
              foreach (var n in current)
              {
                 for( int d=0; d<=9; d++)
                 {
                    var n2 = n * 10 + d;
                    if(n2 % length == 0)
                    {
                       next.Add(n2);
                       Console.WriteLine(n2);
                    }
                 }
              }
              var t = current;
              current = next;
              next = t;
              next.Clear();
           }
        }
     }
  }
added 78 characters in body
Source Link
Jaap Scherphuis
  • 55.7k
  • 8
  • 130
  • 221

The more common name for a Saturday number is

a Polydivisible number

There is a good argument for believing that they cannot grow to any length:

If you remove the last digit from a Polydivisible number you get a smaller Polydivisible number. Conversely, you can only get a length $n$ Polydivisible number if you append a digit $d$ to a length $n-1$ Polydivisible number $q$. For that to work you need $q,d$ to be such that $10q+d\equiv 0 \bmod n$. Only $10$ values are possible for the digit $d$, so no more than $10$ out of $n$ residue classes for $10q \bmod n$ allow this extension to work. Assuming that each residue class is equally probable, the probability that you can extend a Polydivisible number is $10/n$, so when $n>10$ you expected there to be fewer Polydivisible numbers remaining each time you try to extend them.

The longest Saturday number is:

3608528850368400786036725, which is 25 digits long.

To be honest, I wrote a computer program to find it, and only found the common name for this type of number after I googled the number that I found. These numbers are listed in the OEIS.

The more common name for a Saturday number is

a Polydivisible number

There is a good argument for believing that they cannot grow to any length:

If you remove the last digit from a Polydivisible number you get a smaller Polydivisible number. Conversely, you can only get a length $n$ Polydivisible number if you append a digit $d$ to a length $n-1$ Polydivisible number $q$. For that to work you need $q,d$ to be such that $10q+d\equiv 0 \bmod n$. Only $10$ values are possible for the digit $d$, so no more than $10$ out of $n$ residue classes for $10q \bmod n$ allow this extension to work. Assuming that each residue class is equally probable, the probability that you can extend a Polydivisible number is $10/n$, so when $n>10$ you expected there to be fewer Polydivisible numbers remaining each time you try to extend them.

The longest Saturday number is:

3608528850368400786036725, which is 25 digits long.

To be honest, I wrote a computer program to find it, and only found the common name for this type of number after I googled the number that I found.

The more common name for a Saturday number is

a Polydivisible number

There is a good argument for believing that they cannot grow to any length:

If you remove the last digit from a Polydivisible number you get a smaller Polydivisible number. Conversely, you can only get a length $n$ Polydivisible number if you append a digit $d$ to a length $n-1$ Polydivisible number $q$. For that to work you need $q,d$ to be such that $10q+d\equiv 0 \bmod n$. Only $10$ values are possible for the digit $d$, so no more than $10$ out of $n$ residue classes for $10q \bmod n$ allow this extension to work. Assuming that each residue class is equally probable, the probability that you can extend a Polydivisible number is $10/n$, so when $n>10$ you expected there to be fewer Polydivisible numbers remaining each time you try to extend them.

The longest Saturday number is:

3608528850368400786036725, which is 25 digits long.

To be honest, I wrote a computer program to find it, and only found the common name for this type of number after I googled the number that I found. These numbers are listed in the OEIS.

Source Link
Jaap Scherphuis
  • 55.7k
  • 8
  • 130
  • 221

The more common name for a Saturday number is

a Polydivisible number

There is a good argument for believing that they cannot grow to any length:

If you remove the last digit from a Polydivisible number you get a smaller Polydivisible number. Conversely, you can only get a length $n$ Polydivisible number if you append a digit $d$ to a length $n-1$ Polydivisible number $q$. For that to work you need $q,d$ to be such that $10q+d\equiv 0 \bmod n$. Only $10$ values are possible for the digit $d$, so no more than $10$ out of $n$ residue classes for $10q \bmod n$ allow this extension to work. Assuming that each residue class is equally probable, the probability that you can extend a Polydivisible number is $10/n$, so when $n>10$ you expected there to be fewer Polydivisible numbers remaining each time you try to extend them.

The longest Saturday number is:

3608528850368400786036725, which is 25 digits long.

To be honest, I wrote a computer program to find it, and only found the common name for this type of number after I googled the number that I found.