11
$\begingroup$

No weekend love yet shown, therefore I will fix that.

A Saturday number is a number in which for all $1 \le i \le l$, where $l$ is the length of the number, the first $l$ digits (from the left) divide by $l$. For example, 3816547290 is a valid Saturday number for 10, so your answer must, at minimum, be larger than or equal to that. Leading zeroes are not permitted.

If there is a largest Saturday number, find it, else, if there are an infinite number of them, find an example with 200 digits.

$\endgroup$
9
  • 2
    $\begingroup$ should that be the first i digits divide by i? $\endgroup$
    – SteveV
    Jun 16 at 15:07
  • 2
    $\begingroup$ Cross-site duplicate of Find the largest number having this property. $\endgroup$ Jun 17 at 4:48
  • 4
    $\begingroup$ I’m voting to close this question because it already has an answer at math.stackexchange.com/questions/411897/… (cross-site duplicate) $\endgroup$
    – Steve
    Jun 17 at 12:45
  • 1
    $\begingroup$ @Steve Voting to leave open; that's not a reason to close a question on this site. $\endgroup$ Jun 17 at 19:00
  • 1
    $\begingroup$ @JanIvan In general, I'd say what exists or not on another site shouldn't at all affect a question's closability on this site. Same way as we don't close/migrate questions just for being on-topic on another site, if they're also on-topic here. Not sure about any meta guideline though. $\endgroup$ Jun 18 at 10:13
15
$\begingroup$

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.

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();
           }
        }
     }
  }
$\endgroup$
7
  • $\begingroup$ Perfect proof and answer - this is getting accepted. $\endgroup$ Jun 16 at 15:36
  • $\begingroup$ Nice! Could you share a pastebin link or something to your code too? I'm just curious to see how you did that. $\endgroup$ Jun 16 at 15:48
  • 1
    $\begingroup$ @KabirKanhaArora I added my program code. $\endgroup$ Jun 16 at 15:59
  • $\begingroup$ Curiously the OEIS cites the stackexchange network, bringing this full circle! $\endgroup$
    – Steve
    Jun 17 at 12:48
  • $\begingroup$ Now that proof would imply that it might be possible to get bigger if you don't restrict yourself to base 10. I could see a potential OEIS for largest number in base N that meets the criteria... $\endgroup$ Jun 17 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.