27
\$\begingroup\$

The title of Numberphile's newest video, 13532385396179, is a fixed point of the following function \$f\$ on the positive integers:

Let \$n\$ be a positive integer. Write the prime factorization in the usual way, e.g. \60ドル = 2^2 \cdot 3 \cdot 5\$, in which the primes are written in increasing order, and exponents of 1 are omitted. Then bring exponents down to the line and omit all multiplication signs, obtaining a number \$f(n)\$. [...] for example, \$f(60) = f(2^2 \cdot 3 \cdot 5) = 2235\$.

(The above definition is taken from Problem 5 of Five 1,000ドル Problems - John H. Conway)

Note that \$f(13532385396179) = f(13 \cdot 53^2 \cdot 3853 \cdot 96179) = 13532385396179\$.

Task

Take a positive composite integer \$n\$ as input, and output \$f(n)\$.

Another example

\48ドル = 2^4 \cdot 3\$, so \$f (48) = 243\$.

Testcases

More testcases are available here.

 4 -> 22
 6 -> 23
 8 -> 23
 48 -> 243
 52 -> 2213
 60 -> 2235
 999 -> 3337
9999 -> 3211101
caird coinheringaahing ♦
50.9k11 gold badges133 silver badges364 bronze badges
asked Jun 9, 2017 at 9:48
\$\endgroup\$
2
  • 11
    \$\begingroup\$ +1 I'm still astonished that someone managed to find 13532385396179 as a disproof of the conjecture. I guess the 1000ドル prize would go some way to pay for the electricity used! :) \$\endgroup\$ Commented Jun 9, 2017 at 10:21
  • 8
    \$\begingroup\$ Without following the link it wasn't clear that the conjecture is that repeated applications of f(n) will always reach a prime (and of course f(p) = p if p is prime). 13532385396179 disproves the conjecture because it's both composite and a fixed opint. \$\endgroup\$ Commented Jun 9, 2017 at 12:59

21 Answers 21

16
\$\begingroup\$

Python, (削除) 166 (削除ここまで) (削除) 162 (削除ここまで) 159 bytes

You guys are much better. This is what I used! (the algorithm that solved it calls this)

from primefac import*
def c(n):
 x=factorint(n)
 a=''
 for i in range(len(x)):
 l=min(x.keys())
 a+=str(l)
 if x[l]>1:a+=str(x[l])
 x.pop(l)
 return int(a)
answered Jun 9, 2017 at 11:16
\$\endgroup\$
14
  • 2
    \$\begingroup\$ Why did someone downvote a newcomer instead of helping him improve his answer as @LeakyNun did? :( \$\endgroup\$ Commented Jun 9, 2017 at 11:30
  • 3
    \$\begingroup\$ Sorry- that really is what I used (I found the number). I just thought the crummy code would be funny. You can take it down. \$\endgroup\$ Commented Jun 9, 2017 at 11:33
  • 9
    \$\begingroup\$ Welcome on the site. It's really nice to have you sharing with us your solution. (for people who don't know, Jim Davis is the one who solved this problem in the first place). However, answers to challenges need to follow some rules. If you just follow the suggestions from @LeakyNun, then you answer will be valid. (maybe have a look at the other answers to see how they usually look like) \$\endgroup\$ Commented Jun 9, 2017 at 11:47
  • 4
    \$\begingroup\$ Oh my God, I didn't expect Jim Davis himself to appear in this site, and to answer my challenge... I feel so honoured now... \$\endgroup\$ Commented Jun 9, 2017 at 13:15
  • 2
    \$\begingroup\$ ehh, not a troll by the way. My email address is on gladhoboexpress.blogspot.ca/2014/10/climb-to-prime.html ... I left the post up, nobody swamps you with email over math. \$\endgroup\$ Commented Jun 9, 2017 at 13:38
10
\$\begingroup\$

Jelly, 6 bytes

ÆFFḟ1V

Try it online!

Explanation

ÆF Get prime factorisation of input as prime-exponent pairs.
 F Flatten.
 ḟ1 Remove 1s.
 V Effectively flattens the list into a single integer.
answered Jun 9, 2017 at 10:45
\$\endgroup\$
5
  • \$\begingroup\$ V = "concatenate to a single string and eval as Jelly" \$\endgroup\$ Commented Jun 9, 2017 at 10:48
  • \$\begingroup\$ @EriktheOutgolfer Yes, hence "effectively". \$\endgroup\$ Commented Jun 9, 2017 at 10:49
  • \$\begingroup\$ @MartinEnder Any particular reason you don't use Ḍ (Convert from decimal to integer)? \$\endgroup\$ Commented Jul 3, 2017 at 19:00
  • \$\begingroup\$ @Christian Because the list might contain multi-digit integers. \$\endgroup\$ Commented Jul 3, 2017 at 19:26
  • \$\begingroup\$ @MartinEnder Ah, clever. I've used FḌ in the past - that's a good tip! \$\endgroup\$ Commented Jul 4, 2017 at 0:18
9
\$\begingroup\$

Brachylog, 8 bytes

ḋoọc;1xc

Try it online!

Explanation

Example input: 60
ḋ Prime decomposition: [5,3,2,2]
 o Order: [2,2,3,5]
 ọ Occurences: [[2,2],[3,1],[5,1]]
 c Concatenate: [2,2,3,1,5,1]
 ;1x Execute 1s: [2,2,3,5]
 c Concatenate: 2235

You can use N2s (select all integers greater than or equal to 2) instead of ;1x, which is probably more readable and more in the spirit of Brachylog.

answered Jun 9, 2017 at 9:59
\$\endgroup\$
7
\$\begingroup\$

Mathics, 34 bytes

Row[Join@@FactorInteger@#/.1->""]&

Try it online!

-2 bytes from @sanchez

answered Jun 9, 2017 at 9:53
\$\endgroup\$
4
  • 2
    \$\begingroup\$ DeleteCases is long, you can use /.1->"" or /.1->##&[] (alternative form of /.1->Nothing \$\endgroup\$ Commented Jun 9, 2017 at 10:42
  • 3
    \$\begingroup\$ @user202729 All of those need a space in front of the 1 to prevent it from parsing as ... / (0.1). \$\endgroup\$ Commented Jun 9, 2017 at 10:48
  • \$\begingroup\$ You are right! fixed \$\endgroup\$ Commented Jun 9, 2017 at 14:40
  • \$\begingroup\$ Using Join, i.e. Row[Join@@FactorInteger@#/.1->""]& results in 34 bytes \$\endgroup\$ Commented Feb 18, 2021 at 13:14
4
\$\begingroup\$

CJam, 8 bytes

limF:~1-

Try it online!

Explanation

li e# Read input and convert to integer.
mF e# Get prime factorisation as prime-exponent pairs.
:~ e# Flatten.
1- e# Remove 1s.
 e# Implicitly print a flattened representation of the list.
answered Jun 9, 2017 at 10:38
\$\endgroup\$
2
  • \$\begingroup\$ I would have used e_ to flatten, since that's what it's there for, but it doesn't change the score. \$\endgroup\$ Commented Jun 9, 2017 at 14:31
  • 1
    \$\begingroup\$ @PeterTaylor Hm yeah, I can never decide which one to use, but tend to go with e_ for deep flatten only and use :~ whenever it's just a single level. \$\endgroup\$ Commented Jun 9, 2017 at 14:36
4
\$\begingroup\$

05AB1E, 10 bytes

Òγʒ¬?gDië?

Try it online! 

Ò # Push list of prime factors with duplicates
 γ # Break into chunks of consecutive elements
 ʒ # For each
 ¬? # Print the first element
 gD # Push the length of this chunk twice
 ië # If not 1
 ? # Print the length
answered Jun 9, 2017 at 13:34
\$\endgroup\$
3
\$\begingroup\$

05AB1E, (削除) 12 (削除ここまで) 11 bytes

Òγvy¬sg×ばつJ

Try it online!

Explanation

Ò # calculate prime factors with duplicates
 γ # group consecutive equal elements
 vy # for each group
 ¬ # get the head without popping
 sg # push the length of the group
 ×ばつ # repeat the length (length != 1) times
 J # join
answered Jun 9, 2017 at 9:55
\$\endgroup\$
1
  • \$\begingroup\$ Fails for 48. \$\endgroup\$ Commented Jun 9, 2017 at 10:02
2
\$\begingroup\$

Pyth, 12 bytes

smjk_>hddr8P

Try it!

alternative, 12 bytes

smjk<_AdGr8P

Try that!

explanation

smjk_>hddr8P
 PQ # prime factorization (already in correct order) of the implicit input: [3, 3, 11, 101]
 r8 # length encode: [[2, 3], [1, 11], [1, 101]]
 m # map over the length encoded list (lambda variable: d)
 >hdd # take the d[0] last elements of d (so only the last for d[0]==1 and all else)
 _ # reverse that list
 jk # join into a string
s # conatenate the list of strings
answered Jun 9, 2017 at 10:30
\$\endgroup\$
2
\$\begingroup\$

Pyth, 11 bytes

jksm_-d1r8P

Try here

answered Jun 9, 2017 at 11:03
\$\endgroup\$
2
\$\begingroup\$

Python 2, 99 bytes

n=input()
r=''
p=2
while~-n:
 e=0
 while n%p<1:e+=1;n/=p
 r+=str(p)*(e>0)+str(e)*(e>1);p+=1
print r

Try it online!

If inputs are restricted to be below 2147483659, both str(...) may be replaced by `...` saving 6 bytes (this program will be very slow for numbers affected anyway!).

answered Jun 9, 2017 at 15:13
\$\endgroup\$
2
\$\begingroup\$

Ohm, 11 bytes

o:_]D2<?O;J

Try it online!

Explanation

o:_]D2<?O;J
o # Push prime factors with powers from input (Format [[prime,power],...]
 : # For each...
 _ # Push current element
 ] # flatten
 D # Duplicate power
 2<? ; # Is the power smaller than 2?
 O # Delete top of stacks
 J # Join
answered Jun 9, 2017 at 15:33
\$\endgroup\$
1
\$\begingroup\$

Japt, 19 bytes

k ó\ ® ̄1 pZlÃc fÉ q

Test it online!

Explanation

 k ó\ ® ̄ 1 pZlà c fÉ q
Uk ó== mZ{Zs0,1 pZl} c f-1 q // Ungolfed
 // Implicit: U = input number
Uk // Break U into its prime factors.
 ó== // Group into runs of equal items.
 mZ{ } // Map each item Z in this to
 Zs0,1 // Z.slice(0, 1) (the array of the first item),
 pZl // with Z.length added at the end.
 // This returns an array of prime-exponent pairs (Jelly's ÆF).
 c // Flatten.
 f-1 // Filter to the items X where X - 1 is truthy (removes '1's).
 q // Join the resulting array into a single string.
 // Implicit: output result of last expression
answered Jun 9, 2017 at 11:48
\$\endgroup\$
1
\$\begingroup\$

PHP, 88 bytes

for($i=2;1<$a=&$argn;)$a%$i?$i++:$a/=$i+!++$r[$i];foreach($r as$k=>$v)echo$k,$v<2?"":$v;

Try it online!

answered Jun 9, 2017 at 11:00
\$\endgroup\$
1
\$\begingroup\$

R, 72 bytes

x=rle(pracma::factors(scan()));x$l[x$l<2]='';paste0(x$v,x$l,collapse='')

Requires the pracma package, which is not installed on TIO.

answered Jul 3, 2017 at 18:27
\$\endgroup\$
1
+100
\$\begingroup\$

APL (Dyalog Extended), (削除) 15 (削除ここまで) 14 bytes

Saved 1 byte thanks to @Adám

∊⍕ ̈1~⍨∊⍉2⌂pco⎕

Try it online! 

∊⍕ ̈1~⍨∊⍉2⌂pco⎕
 ⎕ ⍝ Input
 2⌂pco ⍝ Prime factors with exponents
 ⍉ ⍝ Transpose so the 1st column is factors, 2nd is exponents
 ∊ ⍝ Flatten
 1~⍨ ⍝ Remove 1
 ⍕ ̈ ⍝ Convert each to a string
∊ ⍝ Concatenate them together
answered Dec 23, 2020 at 16:09
\$\endgroup\$
0
0
\$\begingroup\$

C#, (削除) 206 (削除ここまで) 100 bytes

n=>{var r="";for(int d=1,c;++d<=n;){c=0;while(n%d<1){c++;n/=d;}r+=c>0?d+(c>1?c+"":""):"";}return r;}

Full/Formatted version:

using System;
class P
{
 static void Main()
 {
 Func<int, string> func = n =>
 {
 var r = "";
 for (int d = 1, c; ++d <= n;)
 {
 c = 0;
 while (n % d < 1)
 {
 c++;
 n /= d;
 }
 r += c > 0 ? d + (c > 1 ? c + "" : "") : "";
 }
 return r;
 };
 Console.WriteLine(func(4));
 Console.WriteLine(func(6));
 Console.WriteLine(func(8));
 Console.WriteLine(func(48));
 Console.WriteLine(func(52));
 Console.WriteLine(func(60));
 Console.WriteLine(func(999));
 Console.WriteLine(func(9999));
 Console.ReadLine();
 }
}
answered Jun 9, 2017 at 10:29
\$\endgroup\$
0
\$\begingroup\$

Javascript - 91 bytes

(x,r='',i=1,n)=>{while(x>i++){for(n=0;x%i<1;n++)x/=i;r+=(n>0?i+'':'')+(n>1?n:'')}return r}

Explanation

(x,r='',i=1,n)=>( // input x is the number to process, r, i, n are default values only
 while(x>i++){ // iterate over i until x
 for(n=0;x%i<1;n++) // iterate over n until i is not a factor of x
 x/=i; // factor i out of x
 r+=(n>0?i+'':'') // append i to r if n > 0
 +(n>1?n:'') // append n to r if n > 1
 // i+'' prevents adding i and n before appending to r
 }
 return r // return r by comma-operator and arrow function syntax
)
answered Jun 9, 2017 at 23:57
\$\endgroup\$
0
\$\begingroup\$

Java 8, 103 chars

Pretty straightforward solution.

n->{String r="";int d=2,c;while(n>1){c=0;while(n%d<1){c++;n/=d;}if(c>0)r+=d;if(c>1)r+=c;d++;}return r;}

Ungolfed:

private static Function<Integer, String> f = n->{
 String result = "";
 int divisor = 2, count;
 while (n>1) {
 count = 0;
 while (n % divisor < 1) {
 count++;
 n /= divisor;
 }
 if (count > 0) result += divisor;
 if (count > 1) result += count;
 divisor++;
 }
 return result;
};
answered Jun 10, 2017 at 11:44
\$\endgroup\$
1
  • \$\begingroup\$ 91 bytes \$\endgroup\$ Commented Apr 1, 2019 at 3:41
0
\$\begingroup\$

Octave, 69 bytes

@(a)printf('%d',(f=[[~,c]=hist(b=factor(a),d=unique(b));d](:))(f~=1))

Try it online!

Ended up being quite long, but this will generate the desired output.

Essentially we use the histogram function to count the number of occurrences of the unique values in the prime factorisation of the input value.

  • The result of the factor() function gives the prime factors in ascending order
  • we then find unique() values in that array
  • hist() returns the number of occurrences

Once we have the two arrays (one for unique factors, one for counts), we concatenate the arrays vertically (one on top of the other), and then flatten. This interleaves the factors with counts.

Finally we display the result as a string ensuring to skip any 1's in the final array. The only time 1's can appear is if the count was 1 because 1 will never be a prime factor. This elimination is done before converting to a string so it won't affect things like the number 10.

answered Jun 11, 2017 at 10:03
\$\endgroup\$
0
\$\begingroup\$

Ruby, 45 + 7 bytes

Requires the flag -rprime.

->n{(n.prime_division.flatten-[1]).join.to_i}

Try it online!

answered Jun 11, 2017 at 16:00
\$\endgroup\$
0
\$\begingroup\$

Pyth - 16 bytes

V{PQpNK/PQNItKpK

Try it

Another solution:

sm`d-.nm(d/PQd){PQ1
answered Jun 11, 2017 at 17:29
\$\endgroup\$
2
  • 1
    \$\begingroup\$ One can replace FN by V. \$\endgroup\$ Commented Jun 11, 2017 at 17:34
  • 1
    \$\begingroup\$ Also, r8 (run-length encoding) seems to be useful. \$\endgroup\$ Commented Jun 11, 2017 at 17:35

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.