Problem 52859. Easy Sequences 35: Cutting a donut to Semi-prime pieces

Created by Ramon Villamangca

Solve Later

The figure below illustrates how a torus (donut shape) can be cut in  pieces with only 3 cuts:
                                                
In fact,  is the maximum number of pieces a torus can be sliced with 3 cuts.
Wikipedia's article on Torus, gives an amazing formula for calculating the maximum number of pieces using n number of cuts on a single Torus:
                                                                                
Therefore for : .
Given a cutting limit x, write a function to find all positive integers , such that  is a semi-prime. A semi-prime is a positive integer that has only 2 and exactly 2 prime factors. A few example of semi-primes are: .
As an example for , the only semi-prime 's are  and , therefore the function output should be .

Solve

Solution Stats

41 Solutions
6 Solvers

Last Solution submitted on Nov 17, 2022

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

.M.A. on 28 Oct 2022

For n>330289
something weird happens in this series...
Many more numbers pop up as part of the solution.

For example:
330290 ## 463 * 12970537638763 = 6005358926747269
330321 ## 165161 * 36370874563 = 6007050013699643
330326 ## 2678131 * 2243102671 = 6007322799387901
These 3 examples are semi-primes.
You can check in MATLAB command window:
factor( C(330290) )
factor( C(330321) )
factor( C(330326) )
where C(n) is the equation for the cuts-pieces on a torus.

For this reason, the test 6 of this problem may be wrong and should updated for x=3e5.

GeeTwo on 10 Nov 2022

Actually, factor(C(330290)) would return:
[ 2 5 23 29 33029 27259489]
without rounding errors.

Flintmax ~ 9e15, so if you calculated ~6e15 as n/6, n was clearly above flintmax.

A key point to solve this quickly for large inputs is to notice that any prime factors of n other than 2 or 3 will necessarily be factors of C(n) because the polynomial has a zero constant term.

.M.A. on 14 Nov 2022

@GeeTwo
thank you for pointing out a crucial detail that I was missing!

Solution Comments

Show comments

Problem Recent Solvers6

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 52859. Easy Sequences 35: Cutting a donut to Semi-prime pieces

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers6

Suggested Problems

More from this Author116

Problem Tags

Community Treasure Hunt

Problem 52859. Easy Sequences 35: Cutting a donut to Semi-prime pieces

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers6

Suggested Problems

More from this Author116

Problem Tags

Community Treasure Hunt

Players