24
\$\begingroup\$

If we take a positive integer \$n\$ and write out its factors. Someone can determine \$n\$ just from this list alone. In fact it is trivial to do this since the number is its own largest factor.

However if we take \$n\$ and write only the first half of its factors (factors that are smaller than or equal to \$\sqrt{n}\$), it becomes a lot more difficult to tell the original number from the list alone. In fact, it frequently becomes impossible to tell at all. For example both \$28\$ and \$16\$ give

\$ \begin{array}{ccc} 1 & 2 & 4 \end{array} \$

as the first half of their factors (along with an infinite number of other solutions). So if you show this list to someone they cannot know for sure what your original number was.

But some special cases do have a single unique solution. For example

\$ \begin{array}{ccc} 1 & 2 & 3 & 5 \end{array} \$

is unique to \$30\$. No other number has these as its smaller factors.


The goal of this challenge is to write a program or function which takes as input an integer \$n\$ and determines if the first half of its factors are unique or not.

Your output should be one of two consistent values, one corresponding to inputs that are unique and one to inputs that are not.

This is so answers will be scored in bytes with fewer bytes being the goal.


Test cases

The first 120 truthy values are:

24 30 40 50 56 60 70 80 84 90 98 100 105 108 112 120 126 132 135 140 150 154 162 165 168 176 180 182 189 192 195 196 198 208 210 220 231 234 240 242 252 260 264 270 273 280 286 288 294 297 300 306 308 312 315 320 324 330 336 338 340 351 352 357 360 363 364 374 378 380 384 385 390 396 399 408 416 418 420 429 432 440 442 448 450 455 456 459 462 468 476 480 484 494 495 504 507 510 513 520 528 532 540 544 546 552 560 561 570 572 576 578 585 588 594 595 598 600 608 612

If you want more test cases I've written a reasonably fast generator (generates the first 500 in under 3 seconds on TIO).

Try it online!

For falsy values I recommend you check everything under 50 not on this list, but in particular 12.

\$\endgroup\$
8
  • 5
    \$\begingroup\$ Even without code golf, I think this is a very interesting number-theoretic property? Presumably there are infinitely many such numbers? How frequent are they? \$\endgroup\$ Mar 20 at 4:34
  • 4
    \$\begingroup\$ @JamesK It is not on OEIS I want to do a little more number theoretic work on it before I submit it though, since I have a few small theorems and I think I might be able to prove something nice out of it. \$\endgroup\$
    – Grain Ghost
    Mar 20 at 8:44
  • 1
    \$\begingroup\$ FWIW, I looked at the numbers that increase the ratio \$n_1/n_0\$ where \$n_1\$ is the smallest integer \$>n_0\$ sharing the same half of factors. We get \$[63,147],[325,845],[425,1445],...,[12947,125939],[13189,130691],...\$. For all of them (so far), the half factors consist of two primes \$p<q\$ and we have \$n_1=n_0\times q/p\$, e.g. \$130691=13189\times 109/11\$. \$\endgroup\$
    – Arnauld
    Mar 20 at 14:01
  • 1
    \$\begingroup\$ An interesting number theoretic challenge for anyone: Can you find a number which is not unique but shares its half rainbow with only finite other numbers? If you can't: Can you prove that it is impossible (either a number is unique or infinite)? \$\endgroup\$
    – Grain Ghost
    Mar 20 at 22:15
  • 1
    \$\begingroup\$ rot13 hint: Nal ahzore jvgu n cevzr snpgbe ynetre guna be rdhny gb vgf fdhner ebbg funerf vgf unys envaobj jvgu vasvavgr bgure ahzoref. \$\endgroup\$
    – Grain Ghost
    Mar 20 at 22:15

10 Answers 10

4
\$\begingroup\$

J, 40 bytes

1=1#.]-:&(([#~0=|)~i.#~%:>:i.)"+[:i.1+*:

Try it online!

Here are all test cases, with squaring replaced by 5*x so it finishes on TIO:

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Charcoal, 31 bytes

Nθ≔EX⊕θ²Φ⊕ι∧λ¬∨›Xλ²ι﹪ιλη⁼¹№η§ηθ

Try it online! Link is to verbose version of code. Inefficiently outputs a Charcoal boolean, i.e. - for unique, nothing if not. Explanation:

Nθ

Input n.

≔EX⊕θ²Φ⊕ι∧λ¬∨›Xλ²ι﹪ιλη

For all integers up to (n+1)², list those factors that do not exceed its square root.

⁼¹№η§ηθ

See whether the nth list is unique.

Edit: Switching from (2n)² to (n+1)² made the code an order of magnitude faster without generating false positives. At a cost of 3 bytes, 2+⁴√n⁵ would be even faster; this works because the worst case scenario is of the form p₁²p₂ where p₁<p₂<p₁²; the next integer with the same half rainbow is p₁p₂², and since p₂<p₁² we have p₂³<p₁⁶ and therefore (p₁p₂²)⁴<(p₁²p₂)⁵.

\$\endgroup\$
3
\$\begingroup\$

Haskell, 68 bytes

f n=[x|x<-[1..n],x*x<=n,n`mod`x<1]
g n=[1|x<-[2..n*n],f n==f x]==[1]

Try it online!

  • thanks to @ovs for fixing an error at no cost!

all test cases with 5n instead of n squared to finish on Tio ( @Jonah trick )

\$\endgroup\$
1
2
\$\begingroup\$

Python 3.8, 85 bytes

Based on Noodle9's answer.

The 1<<n is only necessary for n=1, otherwise n*n would be shorter and a lot more efficient.

lambda n:2>(w:=[[a for a in range(x)if x>=a*a>1>x%a]for x in range(1<<n)]).count(w[n])

Try it online! or Try it with n*n!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 80 bytes

n=>(q=t=>t&&q(t-1)+(g(t)==g(n)))(n*n+9)<2
g=n=>(h=i=>i*i>n||h(~-i)+[n%i?'':i])()

Try it online!

Can replace n*n+9 to 2**n in theory but not practical. i in h is negative so concatting lead to something like true-3-2-1 for 12

\$\endgroup\$
2
\$\begingroup\$

Python 3, 103 97 bytes

Saved 6 bytes stealing "borrowing" good golf ideas from ovs's answer!!!

lambda n,d=lambda x:[a for a in range(x)if x>=a*a>1>x%a]:all(d(n)!=d(a)for a in range(n*n)if a-n)

Try it online!

\$\endgroup\$
0
1
\$\begingroup\$

Wolfram Language (Mathematica), 80 bytes

(l=#;Tr[1^(S=Select)[Range[l^2+1],d@#==d@l&]]<2)&
d@n_:=S[Divisors@n,#<=Sqrt@n&]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Excel, 127 bytes

=LET(L,2+A1^1.3,x,SEQUENCE(L),y,SEQUENCE(L^0.5),u,TRANSPOSE(y),z,MMULT((MOD(x,u)=0)*(u<=SQRT(x)),2^y),SUM((INDEX(z,A1)=z)*1)=1)

modified Neil's upper bound to use n^1.3 instead of 1.25 to save a byte. n^2 would use too much memory with this solution.

\$\endgroup\$
2
  • \$\begingroup\$ This is a wonderful solution - I was not aware of the LET(...) command \$\endgroup\$ Mar 22 at 13:09
  • 1
    \$\begingroup\$ Thank you @TaylorScott. LET is relatively new. I still can't use it at work. \$\endgroup\$
    – Axuary
    Mar 22 at 17:18
0
\$\begingroup\$

Jelly, 13 bytes

²‘½ḍƇ$€ċⱮ`⁸ịỊ

A monadic Link accepting a positive integer, \$n\$, that yields 1 if \$n\$ is a unique half rainbow or 0 if not.

Try it online! Or see those up to 60

How?

²‘½ḍƇ$€ċⱮ`⁸ịỊ - Link: integer, n
²             - square (n)
 ‘            - increment
     $€       - for each i in [1..n²+1]:
  ½           -   square root (i)
    Ƈ         -   filter [1..⌊√i⌋] keeping those which:
   ḍ          -     divide (i)
        Ɱ`    - map across itself with:
       ċ      -   count occurrences
          ⁸ị  - get entry at index n
            Ị - is insignificant (effectively = 1?)
\$\endgroup\$
0
\$\begingroup\$

R, 104 88 83 78 74 bytes

m=scan();n=1:m^.5;for(i in 2:m^2)F=F+all(n[!m%%n]==(a<-1:i^.5)[!i%%a]);F<2

Try it online!

following Neil's solution checking for all integers till n².

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I was able to improve on my upper bound by using an inclusive range of 1+n² although I then had to golf it back down to an exclusive range of (1+n)² otherwise my byte-count would have gone up. \$\endgroup\$
    – Neil
    Mar 20 at 12:29
  • \$\begingroup\$ I did not gain any bytes either, but it made my answer about 10 times faster, which means that it could run for higher inputs on TIO. \$\endgroup\$
    – Neil
    Mar 20 at 18:23

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.