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)]

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

Jelly, 21 bytes

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

Try it online!

-1 thanks to Mr. Xcoder.

Returns all possible positions.

Answer 5

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.

Answer 6

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.

Answer 7

05AB1E, 27 21 bytes

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

Try it online!

It returns the lowest 0-indexed p.

Thanks to @Enigma 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

Answer 8

05AB1E, 18 bytes

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

Try it online!

Answer 9

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!

Answer 10

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!

Answer 11

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

Answer 12

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))

Answer 13

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

Answer 14

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.