17
\$\begingroup\$

A curious kid uses a program which can factorize a number or an expression into the following form: p1^e1 * p2^e2 * ... * pn^en . Exponents equal to 1 are omitted e.g. 360 = 2^3 * 3^2 * 5

The kid types this output into the program as new input but they don't understand the ^ sign so sometimes they skip one or more of those concatenating the corresponding prime-base and exponent. E.g. (360 =) 2^3 * 3^2 * 5 => 2^3 * 32 * 5 (= 1280)

Because of these mistakes she might get a different factorization which they can input again (with skipping 0 or more ^'s). They repeat the process until the factorization doesn't change anymore (maybe there are no more ^'s or they copied the output correctly).

You should write a program or function which given an integer n (n>1) outputs all the possible numbers in increasing order whose factorization could be the one the kid ended up with (including n). E.g. for input 16 the possible final factorizations are (16 =) 2^4, (24 =) 2^3 * 3, (23*3 =) 3 * 23

Input details:

  • input is a single integer bigger than 1
  • no input will be given which generates output number greater than 2^31-1
  • no input will be given which generates more than 1000 output numbers

Output details:

  • a list of integers in a convenient form for your language

Examples:

Input => Output

11    => 11
16    => 16 24 69
360   => 140 360 770 1035 1219 1280 2875 3680
605   => 560 605 840 2415
2048  => 211 2048
58564 => 230 456 1311 2508 9975 12768 13794 20748 58564 114114 322102

This is code-golf so shortest program wins.

\$\endgroup\$
4
  • \$\begingroup\$ Don't we already have Factorize It ? \$\endgroup\$
    – Optimizer
    Feb 9, 2015 at 12:00
  • 6
    \$\begingroup\$ @Optimizer This is quite different. \$\endgroup\$
    – randomra
    Feb 9, 2015 at 12:16
  • 1
    \$\begingroup\$ The last number for 360 should be 3680: 2^3*3^2*5 => 23*32*5 = 3680 \$\endgroup\$
    – blutorange
    Feb 9, 2015 at 23:26
  • \$\begingroup\$ @blutorange Thanks, edited. \$\endgroup\$
    – randomra
    Feb 9, 2015 at 23:31

4 Answers 4

5
\$\begingroup\$

CJam - 66

ria{_{:XmF{1=1>},La\{a1$\f++}/La-{XI{~#}%:*/I{si}%:**}fI}%|}1e3*$p

Try it at http://cjam.aditsu.net/

Explanation:

ria                       read token, convert to integer and wrap in array
{…}1e3*                   repeat 1000 times
    _                     duplicate array
    {…}%                  transform each array item (number) using the block
        :X                store the number in X
        mF                factorize with exponents
        {1=1>},           keep only the factors with exponent > 1
        La\{a1$\f++}/     get all the subsets (*)
        La-               remove the empty subset
        {…}fI             for I = each subset of prime factors with exponent > 1
            XI{~#}%:*/    divide X by all the factors in I
            I{si}%:**     multiply with the primes from I
                          concatenated with their exponents
    |                     add the new numbers to the array, removing duplicates
$                         sort
p                         print the final array

(*) Thanks Martin

\$\endgroup\$
5
  • \$\begingroup\$ cjam code from the cjam god \$\endgroup\$
    – kaine
    Feb 10, 2015 at 18:16
  • \$\begingroup\$ Any amount of ^'s could be removed in one step. So for 58564 = 2^2 * 11^4 it should be able to generate 2508 = 22 * 114. \$\endgroup\$
    – randomra
    Feb 10, 2015 at 18:35
  • \$\begingroup\$ @randomra you should add an example for this kind of thing \$\endgroup\$ Feb 10, 2015 at 18:43
  • \$\begingroup\$ @randomra should be better now \$\endgroup\$ Feb 10, 2015 at 20:02
  • \$\begingroup\$ Great! Added the example. Sorry for skipping it. \$\endgroup\$
    – randomra
    Feb 10, 2015 at 20:07
4
\$\begingroup\$

Ruby, 219

To get this started:

s=->(x){A=[];def k(x)A<<x
y=Prime.prime_division x;n=0..y.size-1
n.each{|i|n.to_a.combination(i+1).each{|c|c.each{|z|v=y.dup
v[z][1]>1?v[z]=[v[z].join.to_i,1]:next
k v.inject(1){|s,b|s*b[0]**b[1]}}}}end;k x;A.uniq.sort}

Creates a function s returning an Array of numbers.

https://ideone.com/iOMGny

Use it like this:

#usage

#load from the standard library
require"prime"

#read from stdin and print to stdout
p s.call $<.read.to_i

So much fun writing this all of this on a mobile phone...

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

Perl, 193 bytes

sub R{my($k,$v,@z)=@_;map{$k**$v*$_,$v>1?($k.$v)*$_:()}@z?R(@z):1}
@q=(0+<>);
while($x=pop@q){
my%f;@r=sort{$a<=>$b}@r,$x;
for(2..$x){$x/=$_,$f{$_}++while$x%$_<1}
$_~~@r||push@q,$_ for R%f
}
print"@r"

Newlines are just added for readability.

The for loop factorises the next number ($x) into a hash (%f) of primes and powers. The recursive function (R) uses this hash to generate all the numbers that could be attained by removing ^ signs. These numbers are added to a queue (@q), and the process is repeated by the outer while loop. Each number from the queue is also kept in a unique, sorted array (@r) for printing.

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

Pyth, 46 45 44

Su{smmu*/N^T/PdTv+`T`/PdTkdyft/PdT{PdGU^T3]Q

Try it here.

Fixed the multiple ^ bug. For instance:

Input:  58564
Output: [230, 456, 1311, 2508, 9975, 12768, 13794, 20748, 58564, 114114, 322102]

Note that this code relies on a couple of bugfixes to the official compiler that were pushed after the question was asked. However, it does not use any new language features.

\$\endgroup\$
5
  • \$\begingroup\$ What do you get for 58564? \$\endgroup\$ Feb 10, 2015 at 19:06
  • \$\begingroup\$ [230, 456, 1311, 58564, 322102], which is wrong. \$\endgroup\$
    – isaacg
    Feb 11, 2015 at 0:39
  • \$\begingroup\$ @aditsu Fixed the issue. \$\endgroup\$
    – isaacg
    Feb 11, 2015 at 1:49
  • \$\begingroup\$ As Pyth isn't rigorously documented (based on my findings) it is difficult to distinguish between bug fixes and new features so I decided not to choose this entry as the winning answer. \$\endgroup\$
    – randomra
    Feb 22, 2015 at 13:13
  • \$\begingroup\$ @randomra I understand your decision not to accept this answer. However, I'd just like to mention what the bugfix was: Using a reduce (u) inside another reduce was impossible. I changed a 2 to a 3 in the appropriate location so that reduce would take 3 inputs instead of 2. That's all. \$\endgroup\$
    – isaacg
    Feb 22, 2015 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.