Minimise the count of prime factors through insertion

Question

Given two positive integers A and B, return the position p that minimises the number of prime factors (counting multiplicities) of the resulting integer, when B is inserted in A at p.

For example, given A = 1234 and B = 32, these are the possible insertions (with p being 0-indexed) and the corresponding information about their prime factors:

p | Result | Prime factors         | Ω(N) / Count

0 | 321234 | [2, 3, 37, 1447]      | 4
1 | 132234 | [2, 3, 22039]         | 3
2 | 123234 | [2, 3, 19, 23, 47]    | 5
3 | 123324 | [2, 2, 3, 43, 239]    | 5
4 | 123432 | [2, 2, 2, 3, 37, 139] | 6

You can see that the result has a minimal number of prime factors, 3, when p is 1. So in this particular case, you should output 1.

Specs

If there are multiple positions p that minimise the result, you can choose to output all of them or any one of them.
You may choose 0-indexing or 1-indexing for p, but this choice must be consistent.
A and B can be taken as integers, strings or lists of digits.
You can compete in any programming language and can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default. This is code-golf, so the shortest submission (scored in bytes) wins!

Test cases

A, B -> p (0-indexed) / p (1-indexed)

1234, 32           -> 1 / 2
3456, 3            -> 4 / 5
378, 1824          -> 0 / 1
1824, 378          -> 4 / 5
67, 267            -> Any or all among: [1, 2] / [2, 3]
435, 1             -> Any or all among: [1, 2, 3] / [2, 3, 4]
378100, 1878980901 -> Any or all among: [5, 6] / [6, 7]

For convenience, here is a list of tuples representing each pair of inputs:

[(1234, 32), (3456, 3), (378, 1824), (1824, 378), (67, 267), (435, 1), (378100, 1878980901)]

Can we output the resulting number that has minimized prime factors instead of the index of the insertion? e.g. in your first test case 132234 instead of 1. — dylnan, Jan 10, 2018 at 17:43

ბიმო · Accepted Answer · 2018-01-13 17:22:35Z

Husk, 16 bytes

§◄öLpr§·++⁰↑↓oΘŀ

Expects input as strings, try it online!

Explanation

§◄(öLpr§·++⁰↑↓)(Θŀ)  -- input A implicit, B as ⁰ (example "1234" and "32")
§ (           )(  )  -- apply A to the two functions and ..
  (ö          )      --   | "suppose we have an argument N" (eg. 2)
  (    §      )      --   | fork A and ..
  (         ↑ )      --     | take N: "12"
  (          ↓)      --     | drop N: "34"
  (     ·++⁰  )      --   | .. join the result by B: "123234"
  (   r       )      --   | read: 123234
  (  p        )      --   | prime factors: [2,3,19,23,47]
  ( L         )      --   | length: 5
  (öLpr§·++⁰↑↓)      --   : function taking N and returning number of factors
                            in the constructed number
               ( ŀ)  --   | range [1..length A]
               (Θ )  --   | prepend 0
               (Θŀ)  --   : [0,1,2,3,4]
 ◄                   -- .. using the generated function find the min over range

Community · Accepted Answer · 2020-06-17 09:04:33Z

MATL, 25 bytes

sh"2GX@q:&)1GwhhUYfn]v&X<

Inputs are strings in reverse order. Output is 1-based. If there is a tie the lowest position is output.

Try it online! Or verify all test cases.

Explanation

s         % Implicitly input B as a string. Sum (of code points). Gives a number
h         % Implicitly input A as a string. Concatenate. Gives a string of length
          % N+1, where N is the length of A
"         % For each (that is, do N+1 times)
  2G      %   Push second input
  X@      %   Push 1-based iteration index
  q       %   Subtract 1
  :       %   Range from 1 to that. Gives [] in the first iteration, [1] in
          %   the second, ..., [1 2 ... N] in the last
  &)      %   Two-output indexing. Gives a substring with the selected elements,
          %   and then a substring with the remaining elements
  1G      %   Push first input
  whh     %   Swap and concatenate twice. This builds the string with B inserted
          %   in A at position given by the iteration index minus 1
  U       %   Convert to string
  Yf      %   Prime factors
  n       %   Number of elements
]         % End
v         % Concatenate stack vertically
&X<       % 1-based index of minimum. Implicitly display

score 6 · Accepted Answer · 2018-01-10 18:11:04Z

6

Pyth, 20 13 11 bytes

.mlPsXbQzhl

Try it online

Explanation

.mlPsXbQzhl
.m    b         Find the minimum value...
         hl     ... over the indices [0, ..., len(first input)]...
  lP            ... of the number of prime factors...
    sX Qz       ... of the second input inserted into the first.

edited Jan 10, 2018 at 18:11

answered Jan 10, 2018 at 17:46

user48543

Add a comment |

Erik the Outgolfer · Accepted Answer · 2018-01-10 17:59:01Z

3

Jelly, 21 bytes

D©L‘Ṭœṗ¥€®żF¥€VÆfL€NM

Try it online!

-1 thanks to Mr. Xcoder.

Returns all possible positions.

edited Jan 10, 2018 at 17:59

answered Jan 10, 2018 at 17:55

Erik the Outgolfer

40.5k5 gold badges41 silver badges121 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Japt, 22 21 bytes

This felt far too long as I was writing it up but, looking at some of the other solutions, it actually seems somewhat competitive. Still, there's probably a bit of room for improvement - The cNq) in particular is annoying me. Explanation to follow.

Takes the first input as a string and the second as either an integer or a string. Result is 0-indexed and will return the first index if there are multiple solutions.

ÊÆiYVÃcNq)®°k Ê
b@e¨X

Try it

Explanation

      :Implicit input of string U and integer V.
Ê     :Get the length of U.
Æ     :Generate an array of the range [0,length) and map over each element returning ...
iYV   :  U with V inserted at index Y.
Ã     :End mapping
c     :Append ...
Nq    :  The array of inputs joined to a string.
®     :Map over the array.
°     :Postfix increment - casts the current element to an integer.
k     :Get the prime divisors.
Ê     :Get the length.
\n    :The newline allows the array above to be assigned to variable U.
b     :Get the first index in U that returns true ...
@     :  when passed through a function that ...
e     :    checks that every element in U...
¨     :    is greater than or equal to...
X     :    the current element.
      : Implicit output of resulting integer.

AdmBorkBork · Accepted Answer · 2018-01-10 18:43:53Z

PowerShell, 228 bytes

param($a,$b)function f($a){for($i=2;$a-gt1){if(!($a%$i)){$i;$a/=$i}else{$i++}}}
$p=@{};,"$b$a"+(0..($x=$a.length-2)|%{-join($a[0..$_++]+$b+$a[$_..($x+1)])})+"$a$b"|%{$p[$i++]=(f $_).count};($p.GetEnumerator()|sort value)[0].Name

Try it online!

(Seems long / golfing suggestions welcome. Also times out on TIO for the last test case, but the algorithm should work for that case without issue.)

PowerShell doesn't have any prime factorization built-ins, so this borrows code from my answer on Prime Factors Buddies. That's the first line's function declaration.

We take input $a,$b and then set $p to be an empty hashtable. Next we take the string $b$a, turn it into a singleton array with the comma-operator ,, and array-concatenate that with stuff. The stuff is a loop through $a, inserting $b at every point, finally array-concatenated with $a$b.

At this point, we have an array of $b inserted at every point in $a. We then send that array through a for loop |%{...}. Each iteration, we insert into our hashtable at position $i++ the .count of how many prime factors f that particular element $_ has.

Finally, we sort the hashtable based on values, take the 0th one thereof, and select its Name (i.e., the $i of the index). That's left on the pipeline and output is implicit.

Emigna · Accepted Answer · 2018-01-12 14:46:43Z

2

05AB1E, 18 bytes

gƒ¹õ«N¹g‚£IýÒg})Wk

Try it online!

answered Jan 12, 2018 at 14:46

Emigna

52.9k5 gold badges42 silver badges162 bronze badges

Add a comment |

emanresu A · Accepted Answer · 2021-05-16 08:08:45Z

2

05AB1E, 27 21 bytes

ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk

Try it online!

It returns the lowest 0-indexed p.

Thanks to @Emigna for -6 bytes !

Explanation

ηõ¸ì                  # Push the prefixes of A with a leading empty string -- [, 1, 12, 123, 1234]
    ¹.sRõ¸«)          # Push the suffixes of A with a tailing empty space. -- [1234, 123, 12, 1, ]
            ø         # Zip the prefixes and suffixes
             ε    }   # Map each pair with...
              IýÒg    # Push B, join prefix - B - suffix, map with number of primes
                   Wk # Push the index of the minimum p

edited May 16, 2021 at 8:08

emanresu A

35.6k5 gold badges83 silver badges200 bronze badges

answered Jan 11, 2018 at 11:23

user2956892

1,1595 silver badges9 bronze badges

1

\$\begingroup\$ Using the same method, you could save 6 bytes by rewriting this as ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk. \$\endgroup\$
– Emigna
Jan 12, 2018 at 14:50

Add a comment |

Οurous · Accepted Answer · 2018-01-13 04:33:51Z

1

Clean, 165 ... 154 bytes

import StdEnv,StdLib
@n h#d=hd[i\\i<-[2..h]|h rem i<1]
|d<h= @(n+1)(h/d)=n
?a b=snd(hd(sort[(@0(toInt(a%(0,i-1)+++b+++a%(i,size a))),i)\\i<-[0..size a]]))

Try it online!

edited Jan 13, 2018 at 4:33

answered Jan 10, 2018 at 21:46

Οurous

8,0961 gold badge15 silver badges37 bronze badges

Add a comment |

Jonathan Frech · Accepted Answer · 2018-01-17 15:35:19Z

1

Python 2, 165 146 bytes

Saved nineteen bytes thanks to Erik the Outgolfer.

O=lambda n:n>1and-~O(n/min(d for d in range(2,n+1)if n%d<1))
def f(A,B):L=[int(A[:j]+B+A[j:])for j in range(len(A)+1)];print L.index(min(L,key=O))

Try it online!

edited Jan 17, 2018 at 15:35

answered Jan 10, 2018 at 18:30

Jonathan Frech

7,3411 gold badge21 silver badges43 bronze badges

\$\begingroup\$ 146 bytes \$\endgroup\$
– Erik the Outgolfer
Jan 17, 2018 at 13:47
\$\begingroup\$ @EriktheOutgolfer Thank you. \$\endgroup\$
– Jonathan Frech
Jan 17, 2018 at 15:35

Add a comment |

Arnauld · Accepted Answer · 2018-01-10 18:59:50Z

JavaScript (ES6), 120 bytes

Takes input as 2 strings. Returns a 0-indexed position.

f=(a,b,i=0,m=a)=>a[i>>1]?f(a,b,i+1,eval('for(n=a.slice(0,i)+b+a.slice(i),x=k=2;k<n;n%k?k++:n/=x++&&k);x')<m?(r=i,x):m):r

Test cases

f=(a,b,i=0,m=a)=>a[i>>1]?f(a,b,i+1,eval('for(n=a.slice(0,i)+b+a.slice(i),x=k=2;k<n;n%k?k++:n/=x++&&k);x')<m?(r=i,x):m):r

console.log(f('1234','32'))   // 1
console.log(f('3456','3'))    // 4
console.log(f('378','1824'))  // 0
console.log(f('1824','378'))  // 4
console.log(f('67','267'))    // 1
console.log(f('435','1'))     // 1

Bolce Bussiere · Accepted Answer · 2018-01-11 01:23:44Z

J, 60 Bytes

4 :'(i.<./)#@q:>".@(,(":y)&,)&.>/"1({.;}.)&(":x)"0 i.>:#":x'

Explicit dyad. Takes B on the right, A on the left.

0-indexed output.

Might be possible to improve by not using boxes.

Explanation:

  4 :'(i.<./)#@q:>".@(,(":x)&,)&.>/"1({.;}.)&(":y)"0 i.>:#":y'  | Whole program
  4 :'                                                       '  | Define an explicit dyad
                                                     i.>:#":y   | Integers from 0 to length of y
                                                  "0            | To each element
                                     ({.;}.)&(":y)              | Split y at the given index (result is boxed)
                     (,(":x)&,)&.>/"1                           | Put x inbetween, as a string
                  ".@                                           | Evaluate
                 >                                              | Unbox, makes list
             #@q:                                               | Number of prime factors of each
      (i.>./)                                                   | Index of the minimum

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Python 3, 128 bytes

0-indexed; takes in strings as parameters. -6 bytes thanks to Jonathan Frech.

from sympy.ntheory import*
def f(n,m):a=[sum(factorint(int(n[:i]+m+n[i:])).values())for i in range(len(n)+1)];return a.index(min(a))

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Jan 10, 2018 at 20:46

0WJYxW9FMN

2,76311 silver badges33 bronze badges

\$\begingroup\$ :\n a -> :a. \$\endgroup\$
– Jonathan Frech
Jan 11, 2018 at 23:18

Add a comment |

user84207 · Accepted Answer · 2018-09-13 18:23:00Z

0

Python, 122 bytes

f=lambda n,i=2:n>1and(n%i and f(n,i+1)or 1+f(n/i,i))
g=lambda A,B:min(range(len(A)+1),key=lambda p:f(int(A[:p]+B+A[p:])))

In practice, this exceeds the default max recursion depth pretty quickly.

edited Sep 13, 2018 at 18:23

answered Jan 12, 2018 at 23:12

user84207

1714 bronze badges

Add a comment |

caird coinheringaahin g · Accepted Answer · 2021-03-21 19:44:22Z

Jelly, 16 bytes

;ṭJœṖ€$j€¥VÆfẈNM

Try it online!

Takes A as a list of digits and returns all 1-indices

How it works

;ṭJœṖ€$j€¥VÆfẈNM - Main link. Takes A on the left and B on the right
;                - Concatenate B to the end of A
         ¥       - Group the previous 2 links into a dyad f(A, B):
      $          -   Group the previous 2 links into a monad g(A):
  J              -     Indices of A; [1, 2, ..., len(A)]
     €           -     Over each index:
   œṖ            -       Partition A at that index
        €        -   Over each partition:
       j         -     Join with B
 ṭ               - Append the concatenated number to the end of this list
          V      - Evaluate each as a number
           Æf    - Calculate the prime factors of each
             ẈN  - Get the lengths of each and negate
               M - Indices of maximal elements, which gives the minimal indices when negated

Stack Exchange Network

Minimise the count of prime factors through insertion

Specs

Test cases

15 Answers 15

Husk, 16 bytes

Explanation

MATL, 25 bytes

Explanation

Pyth, 20 13 11 bytes

Explanation

Jelly, 21 bytes

Japt, 22 21 bytes

Explanation

PowerShell, 228 bytes

05AB1E, 18 bytes

05AB1E, 27 21 bytes

Explanation

Clean, 165 ... 154 bytes

Python 2, 165 146 bytes

JavaScript (ES6), 120 bytes

Test cases

J, 60 Bytes

Explanation:

Python 3, 128 bytes

Jelly, 16 bytes

How it works

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
number-theory
primes
integer
or ask your own question.

Linked

Hot Network Questions

Minimise the count of prime factors through insertion

Specs

Test cases

15 Answers 15

Husk, 16 bytes

Explanation

MATL, 25 bytes

Explanation

Pyth, 20 13 11 bytes

Explanation

Jelly, 21 bytes

Japt, 22 21 bytes

Explanation

PowerShell, 228 bytes

05AB1E, 18 bytes

05AB1E, 27 21 bytes

Explanation

Clean, 165 ... 154 bytes

Python 2, 165 146 bytes

JavaScript (ES6), 120 bytes

Test cases

J, 60 Bytes

Explanation:

Python 3, 128 bytes

Jelly, 16 bytes

How it works

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
number-theory
primes
integer
or ask your own question.