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. ;)

Improve this question
1
  • 2
    'I can imagine quite a bit' :)
    – Joseph Wright ♦
    Jul 1, 2021 at 11:01

1 Answer 1

Reset to default
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
Improve this answer
5
  • Et tu, brute-force.
    – Gaussler
    Jul 1, 2021 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, 2021 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, 2021 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, 2021 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, 2021 at 12:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .