Unique half rainbows

Question

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 code-golf 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.

Answer 1

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!

Answer 2

Charcoal, 31 bytes

Ｎθ≔ＥＸ⊕θ²Φ⊕ι∧λ¬∨›Ｘλ²ι﹪ιλη⁼¹№η§ηθ

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

Ｎθ

Input n.

≔ＥＸ⊕θ²Φ⊕ι∧λ¬∨›Ｘλ²ι﹪ιλη

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₂)⁵.

Answer 3

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 )

Answer 4

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!

Answer 5

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!

Answer 6

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

Answer 7

Python 3, ¹⁰³ 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!

Answer 8

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.

Answer 9

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?)

Answer 10

Scala, 97 bytes

Golfed version. Try it online!

def f(n:Int)=(1 to n).filter(x=>x*x<=n&&n%x==0)
def g(n:Int)={(2 to n*n).count(x=>f(n)==f(x))==1}

Answer 11

Vyxal MAB, 17 13 bytes

²›ƛ₌K√ɾ↔;~iOṅ

-4 thanks to @lyxal!
Try it Online!

Answer 12

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².