15
\$\begingroup\$

Problem 4 of the 2025 International Mathematical Olympiad asked (paraphrased):

Let \$f(n)\$ be the sum of the largest three proper divisors of \$n\$, that is divisors excluding \$n\$ itself. For example, \$f(24) = 6 + 8 + 12 = 26\$. Repeatedly apply \$f\$ until you cannot because your current value has fewer than 3 proper divisors. For which starting values of \$n\$ does this process continue forever?

For example, 24 does not work because it gives $$ 24 \to 26 \to 16 \to 14 \to 10 \to 8 \to 7 $$ and 7 has only the proper divisor 1. But, 6 works because it just goes \$ 6 \to 6 \to 6 \to \cdots\$.

These values are OEIS A386276, which starts:

6, 18, 42, 54, 66, 72, 78, 102, 114, 126, 138, 162, 174, 186, 198, 216, 222, 234, 246, 258, 282, 294, 306, 318, 342, 354, 366, 378, 402, 414, 426, 438, 462, 474, 486, 498, 504, 522, 534, 546, 558, 582, 594, 606, 618, 642, 648, 654, 666, 678, 702, 714, 726, 738, 762, 774, 786, 792, 798, 822, 834, 846, 858, 864, 882, 894, 906, 918, 936, 942, 954, 966, 978

Given a positive integer \$n\$, output whether the process continues forever, using either:

  • One of two fixed distinct values indicating "yes" or "no"
  • A truthy or falsy value, as defined by your language (these may be swapped)

The answer to the IMO problem, which you may find useful, is that \$n\$ has the property exactly if its prime factorization

$$ n = 2^{a_2} \cdot 3^{a_3} \cdot 5^{a_5} \cdot 7^{a_7}\cdots $$

satisfies

  • \$a_2\$ is odd
  • \$a_3 \geq (a_2+1)/2 \$
  • \$a_5 = 0 \$

Moreover, these always reach a fixed point -- there are no infinite sequences that reach a cycle or go upwards forever.

Improve this question
\$\endgroup\$
1
  • 8
    \$\begingroup\$ So, \$ 2a_3 > a_2 \$. \$\endgroup\$ Commented Aug 16, 2025 at 4:47

17 Answers 17

Reset to default
15
\$\begingroup\$

Bespoke, 233 bytes

heres a curious problem in math
add of N3of greatest proper divisor;if it does loop,which formulas decide it?simple
just repeat dividing twelve,defining N=division remainder
answer:N divisor six,and of N no divisors constitute five^X

Outputs a truthy value if the given process continues forever, and 0 if it doesn't.

Continually divides by 12 until there's a remainder, and then checks whether the result mod 5 is nonzero and the result mod 6 is zero.

EDIT: Changed N divides six to N divisor six, because the proper way to use the word "divides" here would be "six divides N". This does not change the functionality of the code.

Improve this answer
\$\endgroup\$
8
\$\begingroup\$

Python, 33 bytes

-1 thanks to @Arnauld

f=lambda a:a%5>a%6*6<a%12+f(a/12)

Attempt This Online!

Previous Python, 34 bytes

f=lambda a:a%5>a%6*6<a%12+f(a//12)

Attempt This Online!

Previous Python, 36 bytes

f=lambda a:a%5>a%6<(0<a%12)|f(a//12)

Attempt This Online!

Previous Python, 39 bytes

f=lambda a:a%5>0==a%6<(a%12or f(a//12))

Attempt This Online!

Uses the criteria given at the end of OP.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Would f=lambda a:a%5>a%6*6<a%12+f(a/12) work? \$\endgroup\$ Commented Aug 16, 2025 at 12:28
  • \$\begingroup\$ How does this code terminate? \$\endgroup\$ Commented Aug 16, 2025 at 15:19
  • 1
    \$\begingroup\$ @Ted chained comparisons short circuit in Python. At the very latest once a is <5 the first comparison will fail. \$\endgroup\$ Commented Aug 16, 2025 at 15:39
  • \$\begingroup\$ Ah, I see. I misinterpreted it as (a%5>a%6)*(6<a%12+f(a/12)). Nice! \$\endgroup\$ Commented Aug 17, 2025 at 2:58
  • \$\begingroup\$ @Albert.Lang Your code also works in Python 2. \$\endgroup\$ Commented Aug 18, 2025 at 0:50
5
\$\begingroup\$

JavaScript (ES6), 32 bytes

Port of Albert.Lang's answer.

f=n=>n%5>n%6*6&&n%6<n%12+f(n/12)

Try it online!

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Jelly, 10 bytes

ÆḌṫ-2S��ƬṢƑ

A monadic Link that accepts a positive integer and yields 1 for forever or 0 for terminating.

Try it online! Or see the truthy results up to 50,000.

How?

Instead, consider repeatedly summing the up to three largest proper divisors...

If a number, \$n\$, is divisible by either: $$3 \times 4 = 12$$ $$2 \times 3 \times 5 = 30$$ then the sum of the three largest proper divisors will be greater than \$n\$, with, respectively:

$$f(n) = n(\frac{1}{2} + \frac{1}{3} + \frac{1}{4})$$ $$f(n) = n(\frac{1}{2} + \frac{1}{3} + \frac{1}{5})$$

While, since:

$$\frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1$$ $$\frac{1}{2} + \frac{1}{3} + \frac{1}{7} = \frac{41}{42} < 1$$

...the only way not to decrease when summing the up to three largest proper divisors would be for the number to be divisible by \$6\$ while not satisfying either of the previous cases, whereupon it is a fixed point since now:

$$f(n) = n(\frac{1}{2} + \frac{1}{3} + \frac{1}{6}) = n$$

Thus, the chain of values starting with a forever \$n\$ will either itself be a fixed point or will ascend to a fixed point, while a terminating \$n\$ will, at some point, descend.

ÆḌṫ-2SƲƬṢƑ - Link: positive integer, N
       Ƭ   - collect, starting with k=N, while distinct under:
      Ʋ    -   last four links as a monad - f(k):
ÆḌ         -     proper divisors
  ṫ        -     tail from 1-index...
   -2      -     ...minus two
                   -> up to 3 largest proper divisors of k
     S     -     sum
         Ƒ - is invariant under?:
        Ṣ  -   sort

Original, more direct, method at \$13\$ bytes:

b12t0ḅ12g30⁼6

Try it online!

b12t0ḅ12g30⁼6 - Link: N
b12t0ḅ12      - convert to base 12, trim zeros, convert from base 12
                -> N divided by 12 until no longer possible
        g30   - greatest common divisor of {that} and 30
                -> product of divisors from 2, 3, and 5
           ⁼6 - does {that} equal six?
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

x86 32-bit machine code, 23 22 bytes

99 8D 4A 0C 60 F7 F1 01 D2 74 FA 39 CA 61 75 04 B1 05 F7 F1 92 C3

Try it online!

Following the regparm(1) calling convention, this function takes n as a signed 32-bit integer in EAX and returns a number in EAX, which is nonzero if the process continues forever and zero if it terminates.

In assembly:

f:  cdq             # Set EDX to 0 by sign-extending EAX.
    lea ecx, [edx + 12] # Set ECX to EDX+12 = 12.
    pusha           # Push the values of the general-purpose registers.
r:  div ecx         # Divide EDX:EAX by ECX, which is 12.
                    #  Put the quotient in EAX and the remainder in EDX.
    add edx, edx    # Add EDX to itself, doubling it.
    jz r            # If it's 0, jump back to repeat.
    cmp edx, ecx    # Compare EDX (the doubled remainder) and ECX (12).
    popa            # Restore the pushed register values: EAX=n, EDX=0.
    jnz e           # Jump unless the comparison was equal (remainder 6).
    mov cl, 5       # Set ECX's low byte to 5, making ECX 5.
    div ecx         # Divide EDX:EAX by ECX, which is 5.
                    #  Put the quotient in EAX and the remainder in EDX.
e:  xchg edx, eax   # Exchange EAX and EDX.
    ret             # Return.
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Nekomata + -e, 10 bytes

Äʷ{12¦}¢Gƶ

Attempt This Online! Or see the truthy results up to 100.

Based on this comment on OEIS:

Numbers k of the form 6*i*12^j, where gcd(i, 10) = 1 and j >= 0.

Äʷ{12¦}¢Gƶ
Ä               Multiply by 2
 ʷ{12¦}         Repeatedly divide by 12 until no longer divisible
       ¢G       GCD with 10
         ƶ      Check if the result is 1
Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Given that the \while particle doesn't apply to functions with arity 2, would it make sense to allow the particle to pull an argument from the stack before evaluation? E.g. 12ʷ¦ would function identically to ʷ{12¦} here \$\endgroup\$ Commented Aug 18, 2025 at 17:27
  • 1
    \$\begingroup\$ @ConorO'Brien That's a good idea. I'm planning to add that in some future version. \$\endgroup\$ Commented Aug 19, 2025 at 1:14
  • 1
    \$\begingroup\$ I found ʸ{Ďi↔3T∑ for 8 bytes \$\endgroup\$ Commented Oct 24, 2025 at 1:31
  • 1
    \$\begingroup\$ @hakr14 Nice! You can post it as a separate answer if you want, and I'll give a bounty for outgolfing me in my own language. \$\endgroup\$ Commented Oct 24, 2025 at 2:16
  • 1
    \$\begingroup\$ @alephalpha Heh, thanks! It's a fun language, I'm looking forward to watching it evolve! \$\endgroup\$ Commented Oct 24, 2025 at 2:23
3
\$\begingroup\$

Vyxal, 15 bytes

KṪ3_ȯ₅3=¨i∑0)↔t

Try it Online!

Outputs 0 if falsey, a positive integer if truthy.

Try a test suite mapping the output to explicitly 0 for falsey and 1 for truthy.

Explained

KṪ3_ȯ₅3=¨i∑0)↔t­⁡​‎‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁤⁣‏‏​⁡⁠⁡‌­
            )↔   # ‎⁡Repeat on the input, until the result doesn't change:
KṪ3_ȯ            # ‎⁢  Get the last 3 (3_ == -3) factors of the input
     ₅3=¨i       # ‎⁣  If (¨i) the length is 3:
          ∑      # ‎⁤    Use the sum of the factors as the next input
           0     # ‎⁢⁡  Otherwise, set the next input to 0
              t  # ‎⁢⁢Get the last item of that.
💎

Created with the help of Luminespire.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ This solution hinges on any infinite sequence reaching a fixed point, which is in fact is true -- there's never a cycle, or a sequence that grows forever. \$\endgroup\$ Commented Aug 16, 2025 at 19:19
3
\$\begingroup\$

Re:direction, 31 bytes

+++>
v
++++>
v v
 +++++
 >>> >^

Try it online!

Outputs by exit code, 0 if the process continues forever and 1 (by queue underflow) if it ends.

The input number n initialises the queue with n >s and one v.

The first loop divides by 3, going down at a position determined by the remainder. The next loop similarly divides by 4.

Remainders of (0, 0) lead back to the top-left corner to repeat. Remainders of (0, 2) lead into the third loop to divide by 5, and any remainder other than 2 follows the >s into the bottom-right ^, which points to itself to end execution.

Any other remainders result in entering one of the loops without a v in the queue, which eventually ends with a queue underflow.

Improve this answer
\$\endgroup\$
3
+100
\$\begingroup\$

Nekomata -e, 8 bytes

ʸ{Ďi↔3T∑

Attempt This Online!

Filtering 0-999

Explanation:

ʸ{Ďi↔3T∑ | Full program (-e: output whether a solution exists)
---------+----------------------------------------------------
         | Starting with input,
ʸ{       | Find a fixed point of the following
  Ďi     |  Proper divisors
    ↔3T  |  Last three
       ∑ |  Sum
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 38 21 bytes

ＮθＷ¬﹪θ¹²≧÷¹²θ∧﹪θ⁵¬﹪θ⁶

Try it online! Link is to verbose version of code. Explanation: Now a port of @JosiahWinslow's answer.

Ｎθ

Input n.

Ｗ¬﹪θ¹²≧÷¹²θ

Divide n by 12 as many times as possible.

∧﹪θ⁵¬﹪θ⁶

Check that n is a multiple of 6 but not of 5.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Uiua, 18 bytes

±⍥(/+⍣↙₋₃0⊚=0◿⊸⇡)∞

Try it!
this assumes that all sequences reach fixed points (which is apparently true!)

⍥(   # repeat:
  ◿⊸⇡  # modulo by range
  ⊚=0  # where equals zero
  ⍣    # try:
    ↙₋₃  # take last three
    0    # fail with zero
  /+   # sum
)∞   # until fixed point
±    # sign?
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 11 bytes

·12в0Ü12βT¿

Port of @alephalpha's Nekomata answer, so make sure to upvote that answer as well!

Outputs an 05AB1E truthy/falsey result, which is 1 for truthy, and any other integer (in this case 2, 5 or 10) for falsey.

Try it online or verify all truthy values below 1000 or verify the outputs of all values below 1000.

A more direct implementation of the challenge would be 15 bytes instead:

ΔÑDg4@s¨3.£O*}Ā

Try it online or verify all truthy values below 1000.

And using the prime factorization method explained at the bottom of the challenge, with @Neil's comment in addition to that, would be 13 bytes:

Ó¬É*0ª3£`_·*‹

Try it online or verify all truthy values below 1000.

Explanation:

·          # Double the (implicit) input-integer
 12в       # Then convert it to a base-12 list
    0Ü     # Trim all trailing 0s
      12β  # Convert it back from a base-12 list to a base-10 integer
T¿         # Get the Greatest Common Divisor with 10
           # (after which it is output implicitly as result)

Δ          # Loop until the value no longer changes, using the (implicit) input:
 Ñ         #  Get all divisors of this value
  D        #  Duplicate the list of divisors
   g       #  Pop this copy and push its length
    4@     #  Check that this length is >=4
  s        #  Swap to get the list of divisors again
   ¨       #  Remove the last item (the value itself)
    3.£    #  Then get the last three values of this list of proper divisors
       O   #  Sum them together
        *  #  Multiply it to the earlier length>=4 check
}Ā         # After the changes loop: check that the result is NOT 0
           # (after which the result is output implicitly)

Ó          # Get the prime exponents of the (implicit) input-integer
 ¬         # Push its first exponent (of prime 2) (without popping the list)
  É        # Check whether it is odd
   *       # Multiply that odd-check to each value in the list
 0ª        # Append a 0 in case there are just 1 or 2 items in the list
   3£      # Pop and keep just the first three values
     `     # Pop and push them to the stack
      _    # Check that the top value (exponent of prime 5) is 0
       ·   # Double that check
        *  # Multiply it to the exponent of prime 3
         ‹ # Check that the second value is larger than the first
           # (after which the result is output implicitly)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 107 bytes

f=lambda n,s=[]:1if len(d:=[x for x in range(1,n)if not n%x])<3else 0if(k:=sum(d[-3:]))in s else f(k,s+[k])

Try it online!

Brute force python approach which runs recursively and checks if it has seen a given number before.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ How do you know that having seen a given number before is equivalent to the process continuing forever? It is conceivable that the process can continue forever without numbers ever repeating, isn't it? \$\endgroup\$ Commented Aug 16, 2025 at 15:48
  • \$\begingroup\$ I don't think that's possible. After a certain point, the sum of the largest three divisors will generally be way, WAY smaller than the input, meaning the values have to be constrained to relatively-small numbers. \$\endgroup\$ Commented Aug 16, 2025 at 17:41
  • \$\begingroup\$ Indeed, while it's not apparent from the problem statement, the solution in fact implies that infinite sequences only ever end up repeating a single element. \$\endgroup\$ Commented Aug 16, 2025 at 19:15
  • \$\begingroup\$ Good points. If there was a value which caused it to grow forever this would fail. \$\endgroup\$ Commented Aug 16, 2025 at 22:29
1
\$\begingroup\$

Retina 0.8.2, 49 bytes

.+
$*
+`^(.+)\1{11}$
$1
A`^(.{5})\1*$
^(.{6})\1*$

Try it online! Link includes test cases. Explanation: Another port of @JosiahWinslow's answer.

.+
$*

Convert to unary.

+`^(.+)\1{11}$
$1

Repeatedly divide multiples of 12 by 12.

A`^(.{5})\1*$

Result must not be a multiple of 5.

^(.{6})\1*$

Result must be a multiple of 6.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

APL(NARS), 22 chars

6=30∨{0≠12∣⍵:⍵⋄∇⍵÷12}⎕

Input in stdin the number, output in stdout 1 for the number is in the sequence, else 0. It seems that are in sequence all numbers k: exist i,j

 k=i*12^j and j>=0 and gcd(i,30)=6

It is take one day for understand what Jonathan Allan said in comment...thank you

test:

  6=30∨{0≠12∣⍵:⍵⋄∇⍵÷12}⎕
⎕:
  582
1
  6=30∨{0≠12∣⍵:⍵⋄∇⍵÷12}⎕
⎕:
  583
0
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can avoid the division by six, and the check for divisibility by six, and instead check that the gcd with thirty is equal to six - after repeatedly removing factor sets {2,2,3} (dividing by 12), we need the number to be divisible by six and not divisible by five. \$\endgroup\$ Commented Aug 17, 2025 at 19:42
  • 1
    \$\begingroup\$ (Note that if there are any factors of three left after the divisions by twelve, then there can only be zero or one factors of two left.) \$\endgroup\$ Commented Aug 17, 2025 at 19:52
  • \$\begingroup\$ "n divisible by 6 and not divisible by 5" would be equivalent GCD(n, 30)=6 \$\endgroup\$ Commented Aug 18, 2025 at 10:11
1
\$\begingroup\$

Vyxal 3, 9 bytes

Kᐐ3_⊖∑⊐ᐵt

Vyxal It Online!

v3 doesn't do silly things when doing negative slices longer than a list.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 46 bytes

Golfed version. Try it online!

#~Mod~6==0&&#~Mod~5>0&&(#~Mod~12!=0||d[#/12])&

Ungolfed version. Try it online!

isDivisorSumCandidate[n_Integer] := Module[{current},
  If[n <= 0, Return[False]];
  current = n;
  While[True,
    If[Mod[current, 6] != 0, Return[False]];
    If[Mod[current, 5] == 0, Return[False]];
    If[Mod[current, 12] =!= 0, Return[True]];
    current = Quotient[current, 12];
  ]
]

Do[
  If[isDivisorSumCandidate[i], Print[i]],
  {i, 1, 200}
]
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.