14
\$\begingroup\$

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)]
Improve this question
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I get the feeling this is biased towards 05AB1E... \$\endgroup\$ Commented Jan 10, 2018 at 17:25
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Jan 10, 2018 at 17:43
  • 2
    \$\begingroup\$ @dylnan I am going to say no this time. \$\endgroup\$ Commented Jan 10, 2018 at 17:43

17 Answers 17

Reset to default
8
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
7
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Jelly, 21 bytes

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

Try it online!

-1 thanks to Mr. Xcoder.

Returns all possible positions.

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Japt, 22 21 18 bytes

Takes the first input as a string and the second as either an integer or a string. Output is 0-indexed, returning all matching indices.

Êò@iXV n k Ê ð@e¨X

Try it

Êò@iXV n k Ê\nð@e¨X :Implicit input of string U & integer (or string) V Ê :Length of U ò :Range [0,Ê] @ :Map each X iXV : Insert V in U at 0-based index X (if X=Ê, V gets appended to U) n : Convert to integer k : Prime factors Ê : Length \n :Reassign to U ð :0-based indices that return true (Change to b to get the first index, or a to get the last) @ :When passed through the following function as X e : Is every element in U ¨X : Greater than or equal to U
Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

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, 234, 34, 4, ] ø # 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
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Using the same method, you could save 6 bytes by rewriting this as ηõ¸ì¹.sRõ¸«)øεIýÒg}Wk. \$\endgroup\$ Commented Jan 12, 2018 at 14:50
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 18 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 2, 165 146 bytes

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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 146 bytes \$\endgroup\$ Commented Jan 17, 2018 at 13:47
  • \$\begingroup\$ @EriktheOutgolfer Thank you. \$\endgroup\$ Commented Jan 17, 2018 at 15:35
0
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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))
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ :\n a -> :a. \$\endgroup\$ Commented Jan 11, 2018 at 23:18
0
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 14 bytes

Ug©ÝΣ®‚£XýÒg}н

Try it online or verify (almost) all test cases.

Or alternatively:

ªε+Ns‚£¹ýÒg}Wk

Try it online or verify (almost) all test cases.

Inputs in the order \$B,A\$. Both programs have 0-based outputs.

Explanation:

U # Pop and store the first (implicit) input-integer in variable `X` g # Pop and push the length of the second (implicit) input-integer © # Store this length in variable `®` (without popping) Ý # Pop and push a list in the range [0,length] Σ # Sort it by: ®‚ # Pair the current index with length `®` £ # Split the second (implicit) input into parts of those sizes Xý # Join this pair with `X` as delimiter Ò # Pop and push a list of its prime factors g # Pop and push its length }н # After the sort-by: pop and push the first/smallest one # (which is output implicitly as result) 
ª # Change the second (implicit) input-integer to a list of digits, # and append the first (implicit) input-integer to this list ε # Map over this list: + # Add this value to the second (implicit) input-integer Ns‚ # Pair it with the current 0-based map-index as leading item £ # Split the second (implicit) input into parts of those sizes ¹ý # Join this pair with the first input as delimiter Òg # Same as above: amount of prime factors }W # After the map: push the minimum (without popping) k # Pop and get the (first) 0-based index of this minimum # (which is output implicitly as result)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Vyxal, 86 bitsv2, 10.75 bytes

ẏuJ?vṀǐ@:gḟ

Try it Online!

Bitstring:

10100100010000001010111000010111100110111011011010011001110010111000001110111001001010

Explained

ẏuJ?vṀǐ@:gḟ­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁤‏⁠‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌­ ẏuJ # ‎⁡C = [0...len(A) - 1] concat [-1] ? # ‎⁢Order stack to be A (implicit), C, B vṀ # ‎⁣For each index in C, insert B at position in A. This creates a list of numbers ǐ # ‎⁤Get the prime factors of each, duplicates included @ # ‎⁢⁡Lengths of each :g # ‎⁢⁢Get the minimum without popping 💎

Created with the help of Luminespire.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.