15
\$\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 she doesn't understand the ^ sign so sometimes she skips 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 she can input again (with skipping 0 or more ^'s). She repeats the process until the factorization doesn't change anymore (maybe there are no more ^'s or she 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\$
  • \$\begingroup\$ Don't we already have Factorize It ? \$\endgroup\$ – Optimizer Feb 9 '15 at 12:00
  • 5
    \$\begingroup\$ @Optimizer This is quite different. \$\endgroup\$ – randomra Feb 9 '15 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 '15 at 23:26
  • \$\begingroup\$ @blutorange Thanks, edited. \$\endgroup\$ – randomra Feb 9 '15 at 23:31
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\$
  • \$\begingroup\$ cjam code from the cjam god \$\endgroup\$ – kaine Feb 10 '15 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 '15 at 18:35
  • \$\begingroup\$ @randomra you should add an example for this kind of thing \$\endgroup\$ – aditsu Feb 10 '15 at 18:43
  • \$\begingroup\$ @randomra should be better now \$\endgroup\$ – aditsu Feb 10 '15 at 20:02
  • \$\begingroup\$ Great! Added the example. Sorry for skipping it. \$\endgroup\$ – randomra Feb 10 '15 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\$
  • \$\begingroup\$ What do you get for 58564? \$\endgroup\$ – aditsu Feb 10 '15 at 19:06
  • \$\begingroup\$ [230, 456, 1311, 58564, 322102], which is wrong. \$\endgroup\$ – isaacg Feb 11 '15 at 0:39
  • \$\begingroup\$ @aditsu Fixed the issue. \$\endgroup\$ – isaacg Feb 11 '15 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 '15 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 '15 at 23:00

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.