4

I wrote some code to print the set of divisors but it is not expandable.

\input expl3-generic.tex

\def\divisors#1{%
    \def\L{1}%
    \def\M{#1}%
    \def\x{2}%
    \loop
    \ifnum \fpeval{floor(#1/\x) = #1/\x} = 1\relax
      \edef\L{\L, \x}
      \ifnum \fpeval{\x = #1/\x} = 0 \edef\M{\fpeval{floor(#1/\x)}, \M} \fi
    \fi
    \edef\x{\fpeval{\x + 1}}%
    \ifnum \fpeval{\x > sqrt #1} = 0%
    \repeat
    \L, \M}

\ExplSyntaxOn
\cs_new:Npn \fpeval #1
  { \fp_eval:n { #1 } }
\ExplSyntaxOff

$\divisors{625}$% Prints: 1, 5, 25, 125, 625

\bye

Could you imagine an expandable solution? I know that I could use LuaTeX for this, but programming in TeX is really interesting. ;)

1
  • 2
    'I can imagine quite a bit' :)
    – Joseph Wright
    Jul 1 '21 at 11:01
6

Using a simple brute-force approach

\input expl3-generic.tex

\ExplSyntaxOn
\cs_new:Npn \divisors #1
  {
    1,~
    \__divisors_aux:nn { 2 } {#1}
  }
\cs_new:Npn \__divisors_aux:nn #1#2
  {
    \int_compare:nNnTF {#1} = {#2}
      {#2}
      {
        \fp_compare:nNnT { #2 / #1 } = { floor ( #2 / #1 ) } { #1 , ~ }
        \exp_args:Ne \__divisors_aux:nn { \int_eval:n { #1 + 1 } } {#2}
      }
  }
\ExplSyntaxOff

$\divisors{625}$

\bye

Note that as we need to pass the target value by expansion, we cannot use \int_step_function:nnN (which is expandable), but rather I've programmed in a simple loop myself.

Taking the same ideas, we can use the more efficient loop by also passing the high values as an additional argument

\input expl3-generic.tex

\ExplSyntaxOn
\cs_new:Npn \divisors #1
  {
    1,~
    \__divisors_aux:nnn { 2 } {#1} {#1}
  }
\cs_new:Npn \__divisors_aux:nnn #1#2#3
  {
    \fp_compare:nNnTF {#1} > { sqrt (#2) }
      {#3}
      {
        \fp_compare:nNnTF { #2 / #1 } = { floor ( #2 / #1 ) }
          {
            #1 , ~
            \fp_compare:nNnTF { #1 = #2 / #1 } = 0
              {
                \exp_args:Neee \__divisors_aux:nnn
                  { \int_eval:n { #1 + 1 } } {#2}
                  {
                    \fp_to_int:n { floor ( #2 / #1 ) }
                    , ~ #3
                  }
              }
              {
                \exp_args:Ne \__divisors_aux:nnn
                  { \int_eval:n { #1 + 1 } } {#2} {#3}
              }
          }
          {
            \exp_args:Ne \__divisors_aux:nnn
              { \int_eval:n { #1 + 1 } } {#2} {#3}
          }
      }
  }
\ExplSyntaxOff

$\divisors{625}$

\bye
5
  • Et tu, brute-force.
    – Gaussler
    Jul 1 '21 at 11:03
  • The second version is a lot faster for large values, as it avoids a lot of steps. But of course for smaller input values, that's not so helpful.
    – Joseph Wright
    Jul 1 '21 at 11:18
  • Computer scientists have probably already thought long and deeply about what is the most efficient algorithm. I suspect it would be something like: Find the lowest divisor (which is then automatically prime), then test how many times it divides the number, then divide the number by the highest power and then iterate the algorithm on the quotient, but test only numbers larger than the prime you found before. Continue until you have a prime factorization, then use that for writing out the divisors. Possibly, one could start out by checking a list of known primes.
    – Gaussler
    Jul 1 '21 at 11:23
  • @Gaussler Well yes but in the abstract that doesn't worry about TeX expansion ;) Doing the sqrt is relatively costly, and whilst that's true in general as well as in TeX, there are unique constraints on what we can do easily by expansion.
    – Joseph Wright
    Jul 1 '21 at 11:26
  • True. Plus, you would probably have to sort the divisors in the end, and I understand that sorting is one of the weak points of TeX. P.S. If sqrt is so costly, why don’t you compare #1^2 to #2 instead? ;-)
    – Gaussler
    Jul 1 '21 at 12:11

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.