Challenge: Rhonda Numbers
A Rhonda number is a positive integer n that satisfies the property that, for a given base b, the product of the base-b digits of n is equal to b times the sum of n's prime factors. Only composite bases (non-prime bases) have Rhonda numbers.
For instance, consider 10206₁₀ = 2133132₄, that is, 2×4⁶ + 1×4⁵ + 3×4⁴ + 3×4³ + 1×4² + 3×4¹ + 2×4⁰ = 2×4096₁₀ + 1×1024₁₀ + 3×256₁₀ + 3×64₁₀ + 1×16₁₀ + 3×4₁₀ + 2 = 8192₁₀ + 1024₁₀ + 768₁₀ + 192₁₀ + 16₁₀ + 12₁₀ + 2 = 10206₁₀. 10206₁₀ has the prime factorization (2, 3, 3, 3, 3, 3, 3, 7) because 2×3⁶×7 = 10206₁₀. This is a base-4 Rhonda number because 2×1×3×3×1×3×2 = 108₁₀ and 4×(2+3+3+3+3+3+3+7) = 4×27₁₀ = 108₁₀.
The Wolfram MathWorld entry for “Rhonda Number” provides tables of many Rhonda numbers. Further information on Rhonda numbers may be found at Numbers Aplenty. You may also find this base conversion tool helpful.
Produce three files to carry out this task:
/lib/rhonda/hoonYour library
/lib/rhonda/hoonshould expose two arms:++checkaccepts a@udunsigned decimal value for the base and a@udunsigned decimal value for the number, and returns%.yor%.ndepending on whether the given number is a Rhonda number in that base or not.++seriesaccepts a base as a@udunsigned decimal value and a number of values to returnn, and either returns~if the base is prime or thenfirst Rhonda numbers in that base.
/gen/rhonda-check/hoonYou should provide a
%saygenerator at/gen/rhonda-check/hoonwhich accepts a@udunsigned decimal value and applies++checkto verify if that value is a Rhonda number or not./gen/rhonda-series/hoonYou should provide a
%saygenerator at/gen/rhonda-series/hoonwhich accepts a@udunsigned decimal valueband a@udunsigned decimal valuen, wherebis the base b, and returns the first n Rhonda numbers in that base.
Unit Tests
Following a principle of test-driven development, we compose a series of tests which allow us to rigorously check for expected behavior.
/+ *test, *rhonda|%++ test-check-four;: weld%+ expect-eq!> %.n!> (check 4 10.000)%+ expect-eq!> %.y!> (check 4 10.206)%+ expect-eq!> %.n!> (check 4 10.500)%+ expect-eq!> %.y!> (check 4 11.935)%+ expect-eq!> %.n!> (check 4 50.000)%+ expect-eq!> %.y!> (check 4 94.185)==++ test-check-six;: weld%+ expect-eq!> %.n!> (check 6 800)%+ expect-eq!> %.y!> (check 6 855)%+ expect-eq!> %.n!> (check 6 1.000)%+ expect-eq!> %.y!> (check 6 1.029)%+ expect-eq!> %.n!> (check 6 18.181)%+ expect-eq!> %.y!> (check 6 19.136)==++ test-check-eight;: weld%+ expect-eq!> %.n!> (check 8 1.200)%+ expect-eq!> %.y!> (check 8 1.836)%+ expect-eq!> %.n!> (check 8 4.800)%+ expect-eq!> %.y!> (check 8 6.622)%+ expect-eq!> %.n!> (check 8 18.181)%+ expect-eq!> %.y!> (check 8 25.398)==++ test-check-nine;: weld%+ expect-eq!> %.n!> (check 9 15.000)%+ expect-eq!> %.y!> (check 9 15.540)%+ expect-eq!> %.n!> (check 9 20.000)%+ expect-eq!> %.y!> (check 9 21.054)%+ expect-eq!> %.n!> (check 9 45.000)%+ expect-eq!> %.y!> (check 9 47.652)==++ test-check-ten;: weld%+ expect-eq!> %.n!> (check 10 1.000)%+ expect-eq!> %.y!> (check 10 1.568)%+ expect-eq!> %.n!> (check 10 2.000)%+ expect-eq!> %.y!> (check 10 2.835)%+ expect-eq!> %.n!> (check 10 12.000)%+ expect-eq!> %.y!> (check 10 12.985)==++ test-check-twelve;: weld%+ expect-eq!> %.n!> (check 12 500)%+ expect-eq!> %.y!> (check 12 560)%+ expect-eq!> %.n!> (check 12 1.000)%+ expect-eq!> %.y!> (check 12 3.993)%+ expect-eq!> %.n!> (check 12 50.000)%+ expect-eq!> %.y!> (check 12 58.504)==++ test-series-three;: weld%+ expect-eq!> ~!> (series 3 5)==++ test-series-four;: weld%+ expect-eq!> `(list @ud)`~[10.206]!> (series 4 1)%+ expect-eq!> `(list @ud)`~[10.206 11.935 12.150 16.031]!> (series 4 4)%+ expect-eq!> `(list @ud)`~[10.206 11.935 12.150 16.031 45.030 94.185]!> (series 4 6)==++ test-series-six;: weld%+ expect-eq!> `(list @ud)`~[855]!> (series 6 1)%+ expect-eq!> `(list @ud)`~[855 1.029 3.813 5.577]!> (series 6 4)%+ expect-eq!> `(list @ud)`~[855 1.029 3.813 5.577 7.040 7.304]!> (series 6 6)==++ test-series-nine;: weld%+ expect-eq!> `(list @ud)`~[15.540]!> (series 9 1)%+ expect-eq!> `(list @ud)`~[15.540 21.054 25.331]!> (series 9 3)%+ expect-eq!> `(list @ud)`~[15.540 21.054 25.331 44.360 44.660 44.733 47.652]!> (series 9 7)==++ test-series-ten;: weld%+ expect-eq!> `(list @ud)`~[1.568]!> (series 10 1)%+ expect-eq!> `(list @ud)`~[1.568 2.835 4.752 5.265 5.439 5.664 5.824]!> (series 10 7)%+ expect-eq!> `(list @ud)`~[1.568 2.835 4.752 5.265 5.439 5.664 5.824 5.832 8.526 12.985]!> (series 10 10)==++ test-series-sixteen;: weld%+ expect-eq!> `(list @ud)`~[1.000 1.134]!> (series 16 2)%+ expect-eq!> `(list @ud)`~[1.000 1.134 6.776 15.912 19.624]!> (series 16 5)%+ expect-eq!> `(list @ud)`~[1.000 1.134 6.776 15.912 19.624 20.043 20.355 23.946 26.296]!> (series 16 9)==--
Solutions
These solutions were submitted by the Urbit community as part of a competition in ~2022.6. They are made available under both the MIT license and the CC0 license. We ask you to acknowledge authorship should you utilize these elsewhere.
Solution #1
This solution was produced by ~mocmex-pollen. This code includes the ~_ sigcab error message rune and demonstrates the use of a helper core in a library and shows ^ ket skipping of $ buc.
/lib/rhonda.hoon
:::: A library for producing Rhonda numbers and testing if numbers are Rhonda.:::: A number is Rhonda if the product of its digits of in base b equals:: the product of the base b and the sum of its prime factors.:: see also: https://mathworld.wolfram.com/RhondaNumber.html::=<::|%:: +check: test whether the number n is Rhonda to base b::++ check|= [b=@ud n=@ud]^- ?~_ leaf+"base b must be >= 2"?> (gte b 2)~_ leaf+"candidate number n must be >= 2"?> (gte n 2)::.= (roll (base-digits b n) mul)%+ mulb(roll (prime-factors n) add):: +series: produce the first n numbers which are Rhonda in base b:::: produce ~ if base b has no Rhonda numbers::++ series|= [b=@ud n=@ud]^- (list @ud)~_ leaf+"base b must be >= 2"?> (gte b 2)::?: =((prime-factors b) ~[b])~=/ candidate=@ud 2=+ rhondas=*(list @ud)|-?: =(n 0)(flop rhondas)=/ is-rhonda=? (check b candidate)%= $rhondas ?:(is-rhonda [candidate rhondas] rhondas)n ?:(is-rhonda (dec n) n)candidate +(candidate)==--::|%:: +base-digits: produce a list of the digits of n represented in base b:::: This arm has two behaviors which may be at first surprising, but do not:: matter for the purposes of the ++check and ++series arms, and allow for:: some simplifications to its implementation.:: - crashes on n=0:: - orders the list of digits with least significant digits first:::: ex: (base-digits 4 10.206) produces ~[2 3 1 3 3 1 2]::++ base-digits|= [b=@ud n=@ud]^- (list @ud)?> (gte b 2)?< =(n 0)::|-?: =(n 0)~:- (mod n b)$(n (div n b)):: +prime-factors: produce a list of the prime factors of n:::: by trial division:: n must be >= 2:: if n is prime, produce ~[n]:: ex: (prime-factors 10.206) produces ~[7 3 3 3 3 3 3 2]::++ prime-factors|= [n=@ud]^- (list @ud)?> (gte n 2)::=+ factors=*(list @ud)=/ wheel new-wheel:: test candidates as produced by the wheel, not exceeding sqrt(n)::|-=^ candidate wheel (next:wheel)?. (lte (mul candidate candidate) n)?:((gth n 1) [n factors] factors)|-?: =((mod n candidate) 0):: repeat the prime factor as many times as possible::$(factors [candidate factors], n (div n candidate))^$:: +new-wheel: a door for generating numbers that may be prime:::: This uses wheel factorization with a basis of {2, 3, 5} to limit the:: number of composites produced. It produces numbers in increasing order:: starting from 2.::++ new-wheel=/ fixed=(list @ud) ~[2 3 5 7]=/ skips=(list @ud) ~[4 2 4 2 4 6 2 6]=/ lent-fixed=@ud (lent fixed)=/ lent-skips=@ud (lent skips)::|_ [current=@ud fixed-i=@ud skips-i=@ud]:: +next: produce the next number and the new wheel state::++ next|.:: Exhaust the numbers in fixed. Then calculate successive values by:: cycling through skips and increasing from the previous number by:: the current skip-value.::=/ fixed-done=? =(fixed-i lent-fixed)=/ next-fixed-i ?:(fixed-done fixed-i +(fixed-i))=/ next-skips-i ?:(fixed-done (mod +(skips-i) lent-skips) skips-i)=/ next?. fixed-done(snag fixed-i fixed)(add current (snag skips-i skips)):- next+.$(current next, fixed-i next-fixed-i, skips-i next-skips-i)----
/gen/rhonda-check.hoon
:: %say the product of the check arm of /lib/rhonda/hoon::/+ *rhonda:::- %say|= [* [b=@ud n=@ud ~] *]^- [%noun ?][%noun (check b n)]
/gen/rhonda-series.hoon
:: %say the product of the series arm of /lib/rhonda/hoon::/+ *rhonda:::- %say|= [* [b=@ud n=@ud ~] *]^- [%noun (list @ud)][%noun (series b n)]
Solution #2
This solution was produced by ~ticlys-monlun. This code demonstrates using a ++map data structure and a different square-root solution algorithm.
/lib/rhonda.hoon
|%++ check|= [n=@ud base=@ud]:: if base is prime, automatic no::?: =((~(gut by (prime-map +(base))) base 0) 0)%.n:: if not multiply the digits and compare to base x sum of factors::?: =((roll (digits [base n]) mul) (mul base (roll (factor n) add)))%.y%.n++ series|= [base=@ud many=@ud]=/ rhondas *(list @ud)?: =((~(gut by (prime-map +(base))) base 0) 0)rhondas=/ itr 1|-?: =((lent rhondas) many)(flop rhondas)?: =((check itr base) %.n)$(itr +(itr))$(rhondas [itr rhondas], itr +(itr)):: digits: gives the list of digits of a number in a base:::: We strip digits least to most significant.:: The least significant digit (lsd) of n in base b is just n mod b.:: Subtract the lsd, divide by b, and repeat.:: To know when to stop, we need to know how many digits there are.++ digits|= [base=@ud num=@ud]^- (list @ud)|-=/ modulus=@ud (mod num base)?: =((num-digits base num) 1)~[modulus][modulus $(num (div (sub num modulus) base))]:: num-digits: gives the number of digits of a number in a base:::: Simple idea: k is the number of digits of n in base b if and:: only if k is the smallest number such that b^k > n.++ num-digits|= [base=@ud num=@ud]^- @ud=/ digits=@ud 1|-?: (gth (pow base digits) num)digits$(digits +(digits)):: factor: produce a list of prime factors:::: The idea is to identify "small factors" of n, i.e. prime factors less than:: the square root. We then divide n by these factors to reduce the:: magnitude of n. It's easy to argue that after this is done, we obtain 1:: or the largest prime factor.::++ factor|= n=@ud^- (list @ud)?: ?|(=(n 0) =(n 1))~[n]=/ factorization *(list @ud):: produce primes less than or equal to root n::=/ root (sqrt n)=/ primes (prime-map +(root)):: itr = iterate; we want to iterate through the primes less than root n::=/ itr 2|-?: =(itr +(root)):: if n is now 1 we're done::?: =(n 1)factorization:: otherwise it's now the original n's largest primes factor::[n factorization]:: if itr not prime move on::?: =((~(gut by primes) itr 0) 1)$(itr +(itr)):: if it is prime, divide out by the highest power that divides num::?: =((mod n itr) 0)$(n (div n itr), factorization [itr factorization]):: once done, move to next prime::$(itr +(itr)):: sqrt: gives the integer square root of a number:::: Yes, this is a square root algorithm I wrote just because.:: It's based on an algorithm that predates the Greeks::: To find the square root of A, think of A as an area.:: Guess the side of the square x. Compute the other side y = A/x.:: If x is an over/underestimate then y is an under/overestimate.:: So (x+y)/2 is the average of an over and underestimate, thus better than x.:: Repeatedly doing x --> (x + A/x)/2 converges to sqrt(A).:::: This algorithm is the same but with integer valued operations.:: The algorithm either converges to the integer square root and repeats,:: or gets trapped in a two-cycle of adjacent integers.:: In the latter case, the smaller number is the answer.::++ sqrt|= n=@ud=/ guess=@ud 1|-=/ new-guess (div (add guess (div n guess)) 2):: sequence stabilizes::?: =(guess new-guess)guess:: sequence is trapped in 2-cycle::?: =(guess +(new-guess))new-guess?: =(new-guess +(guess))guess$(guess new-guess):: prime-map: (effectively) produces primes less than a given input:::: This is the sieve of Eratosthenes to produce primes less than n.:: I used a map because it had much faster performance than a list.:: Any key in the map is a non-prime. The value 1 indicates "false.":: I.e. it's not a prime.++ prime-map|= n=@ud^- (map @ud @ud)=/ prime-map `(map @ud @ud)`(my ~[[0 1] [1 1]]):: start sieving with 2::=/ sieve 2|-:: if sieve is too large to be a factor we're done::?: (gte (mul sieve sieve) n)prime-map:: if not too large but not prime, move on::?: =((~(gut by prime-map) sieve 0) 1)$(sieve +(sieve)):: sequence: explanation:::: If s is the sieve number, we start sieving multiples:: of s at s^2 in sequence: s^2, s^2 + s, s^2 + 2s, ...:: We start at s^2 because any number smaller than s^2:: has prime factors less than s and would have been:: eliminated earlier in the sieving process.::=/ sequence (mul sieve sieve)|-:: done sieving with s once sequence is past n::?: (gte sequence n)^$(sieve +(sieve)):: if sequence position is known not prime we move on::?: =((~(gut by prime-map) sequence 0) 1)$(sequence (add sequence sieve)):: otherwise we mark position of sequence as not prime and move on::$(prime-map (~(put by prime-map) sequence 1), sequence (add sequence sieve))--
/gen/rhonda-check.hoon
/+ *rhonda:- %say|= [* [n=@ud base=@ud ~] ~]:- %noun(check n base)
/gen/rhonda-series.hoon
/+ *rhonda:- %say|= [* [base=@ud many=@ud ~] ~]:- %noun(series base many)
Solution #3
This solution was produced by ~tamlut-modnys. This code demonstrates a clean prime factorization algorithm and the use of ++roll.
/lib/rhonda.hoon
|%:::: check if a given input is a Rhonda number for a given base::++ check|= [base=@ud num=@ud]^- ??: (lte base 1)!!=((roll (get-base-digits base num) mul) (mul base (roll (prime-factors num) add))):::: returns the first n Rhonda numbers in a base or ~ if the base is prime::++ series|= [base=@ud n=@ud]^- (list @ud)?: (lte base 1)!!:: checking if the base is prime.::?: =((prime-factors base) ~[base])~:: variable for the output::=/ result *(list @ud):: iteration variable to check if it's a Rhonda number::=/ iter 1:: iteration variable in base digit representation as a list, to save time by preventing repeated conversion::=/ iterbase (limo [1 ~]):: length variable to prevent repeated calls of lent on the result::=/ length 0|-:: output if finished::?: =(length n)(flop result):: check if the current number is a Rhonda number in the base::?: =((roll iterbase mul) (mul base (roll (prime-factors iter) add))):: if so add it to the result and check higher::$(result [iter result], length +(length), iter +(iter), iterbase (increment-num-in-base iterbase base)):: otherwise just check higher::$(iter +(iter), iterbase (increment-num-in-base iterbase base)):::: returns the base decomposition of a number as a list of digits::++ get-base-digits|= [base=@ud num=@ud]^- (list @ud)?: (lte base 1)!!:: define the output::=/ result *(list @ud)|-:: loop until there are no more digits::?: =(num 0)(flop result)=/ division (dvr num base):: divide the number by the base, prepend the remainder to the result and loop::$(result [q.division result], num p.division):::: returns the prime factorization of a number as a list::++ prime-factors|= num=@ud^- (list @ud):: define the output::=/ result *(list @ud):: used to iterate on possible prime factors starting from 2::=/ iter 2|-:: if the number is 1, there are no more factors::?: =(num 1)result:: divide the number by the current factor, get result and remainder::=/ division (dvr num iter):: if it divides cleanly, then add the current factor to the list of prime factors and loop on the result::?: =(q.division 0)$(num p.division, result [iter result]):: if the current factor is greater than the square root of the number, then add the number as a factor and terminate::?: (gth iter p.division)[num result]:: in all other cases just increment the factor and keep testing::$(iter +(iter)):::: increments a base decomposition of a number (a list of digits) by 1.:: this functionality is implemented to speed up the series function and avoid repeated calls to get-base-digits::++ increment-num-in-base:: input is a number as a list of digits and a base::|= [num=(list @ud) base=@ud]^- (list @ud):: length variable to avoid repeated calls to lent::=/ length (lent num):: iterate to potentially carry a digit when adding::=/ index 0|-:: if we carry a digit to the end (e.g. 999 + 1) then append a 1::?: =(index length)(snoc num 1):: incrementation::=/ num (snap num index (add (snag index num) 1)):: if we need to carry a digit::?: (gte (snag index num) base):: then make the current digit 0 and loop::$(index +(index), num (snap num index 0)):: otherwise return the incremented number::num--
/gen/rhonda-check.hoon
:: say generator that calls the check function to see if a number is a Rhonda number::/+ rhonda:- %say|= [* [base=@ud n=@ud ~] *]:- %noun(check:rhonda [base n])
/gen/rhonda-series.hoon
:: say generator that calls the series function to get the first n Rhonda numbers in a base::/+ rhonda:- %say|= [* [base=@ud n=@ud ~] *]:- %noun(series:rhonda [base n])
Solution #4
This solution was produced by ~sidnym-ladrut. This code demonstrates using multiple cores in a library.
/lib/rhonda.hoon
:: rhonda number validator/generator:: https://www.numbersaplenty.com/set/Rhonda_number/::|%++ as-base :: convert n to base b|= [b=@ud n=@ud]^- (list @ud)=+ p=(log-base b n)=| l=(list @ud)|-?: =(p 0)[n l]=+ btop=(pow b p)=+ next=(div n btop)$(p (dec p), n (sub n (mul next btop)), l [next l])++ log-base :: b-based unsigned log of value n|= [b=@ud n=@ud]^- @ud=+ p=1|-?: (lth n (pow b p))(dec p)$(p +(p))++ prime-factors :: prime number factors of n|= n=@ud^- (list @ud)~+=| l=(list @ud)=/ i=@ud 2|-?: (gth i -:(sqt n))?: (gth n 2)[n l]l|-?: !=((mod n i) 0)^$(i +(i))$(n (div n i), l [i l])++ is-prime :: is given @ud a prime number?|= n=@ud^- bean~+?: (lte n 1) %.n?: (lte n 3) %.y%+ levy (gulf 2 -:(sqt n))|=(i=@ud !=((mod n i) 0))--::|%++ check :: check if n is rhonda in base b:: rhonda(b, n) := Π_digits(n_b) == b * Σ_values(prime-factors(n))|= [b=@ud n=@ud]^- bean:: https://mathworld.wolfram.com/RhondaNumber.html:: "Rhonda numbers exist only for bases that are composite since:: there is no way for the product of integers less than a prime b:: to have b as a factor."?: (is-prime b)%.n=+ baseb=(as-base b n)=+ facts=(prime-factors n).= (roll baseb mul)(mul b (roll facts add))++ series :: list first n rhondas of base b|= [b=@ud n=@ud]^- (list @ud)=| l=(list @ud)=/ i=@ud 2=/ c=@ud 0?: (is-prime b)l|-?: =(c n)(flop l)?. (check b i)$(i +(i))$(i +(i), c +(c), l [i l])
/gen/rhonda-check.hoon
/+ *rhonda:- %say|= [* [n=@ud ~] ~]:- %noun^- bean:: 4 is the minimum rhonda base (lowest non-prime integer).:: n is *a* maximum because n != n * (v >= 2), but likely not the best maximum.?& (gte n 4)%+ lien (gulf 4 n)|= b=@ud^- bean(check b n)==
/gen/rhonda-series.hoon
/+ *rhonda:- %say|= [* [b=@ud n=@ud ~] ~]:- %noun^- (list @ud)(series b n)