17
\$\begingroup\$

Given an integer p > 1, find the smallest integer q > p such that the list of exponents in the prime factorization of q is the same of that of p, no matter the order or the value of the prime factors.

Examples

The prime factorization of p = 20 is 22 x 51. The smallest integer greater than p with identical exponents in its prime factorization is q = 28 = 22 x 71.

The prime factorization of p = 2500 is 22 x 54. The smallest integer greater than p with identical exponents in its prime factorization is q = 2704 = 24 x 132.

Rules

  • The input is guaranteed to be an integer greater than 1.
  • This is , so the shortest answer in bytes wins.

Test cases

Input | Output
------+-------
2     | 3
20    | 28
103   | 107
256   | 6561
768   | 1280
2500  | 2704
4494  | 4510
46552 | 46584
75600 | 105840
\$\endgroup\$
  • 2
    \$\begingroup\$ Just for reference, this is A081761 in the OEIS. \$\endgroup\$ – Jonathan Frech Oct 1 '17 at 20:43

10 Answers 10

9
\$\begingroup\$

Husk, 10 bytes

§ḟ¤≡ȯÖLgp→

Try it online!

Explantion

§ḟ       →     Find the first number starting from the input + 1 such that...
        p        The prime factorisation
       g         with equal elements grouped together
    ȯÖL          and sorted by length of groups
  ¤≡             has the same shape as the above applied to the input.
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 61 bytes

(f[x_]:=Sort[Last/@FactorInteger@x];s=#;While[f@++s!=f@#];s)&  

Try it online!

-4 bytes from @Misha Lavrov

\$\endgroup\$
  • \$\begingroup\$ A more concise way of writing such a While loop is s=#;While[f@++s!=f@#];s. \$\endgroup\$ – Misha Lavrov Oct 1 '17 at 21:45
  • 1
    \$\begingroup\$ You can replace f[x_] with f@x_ to save a byte. \$\endgroup\$ – numbermaniac Oct 2 '17 at 0:12
  • 1
    \$\begingroup\$ Or even go the composition-salad route of defining f=Last/@#&@*FactorInteger/*Sort. \$\endgroup\$ – Misha Lavrov Oct 2 '17 at 2:23
4
\$\begingroup\$

Pyth, 15 bytes

fqFmShMrPd8,QTh

Try it here! or Verify all the test cases.

How does this work?

fqFmShMrPd8,QTh   ~ Full program. Q = first input.

f             h   ~ First input where the condition is truthy over [Q+1, Q+2, ...]
           ,QT    ~ The two element list [Q, current value (T)].
   m              ~ Map over ^ with d.
       Pd         ~ The prime factorization of d.
      r  8        ~ Run-Length encode ^.
    hM            ~ Get the first element of each.
 qF               ~ Check if the values are equal.
                  ~ Output implicitly.

Alternatives

Another 15-byter:

LShMrPb8fqyQyTh

And a couple of (longer) alternatives:

fqFmSlM.gkPd,QTh
LSlM.gkPbfqyQyTh
LS/LPb{PbfqyQyTh
f!-FmlM.gkPd,QTh
\$\endgroup\$
4
\$\begingroup\$

Jelly, 15 14 bytes

1 byte thanks to Erik the Outgolfer.

ÆEḟ0Ṣ
,Ç€Eð2#Ṫ

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Brachylog, 13 bytes

<.;?{ḋḅlᵐ}ᵐ=∧

Try it online!

It's been a long time since I posted an answer…

Explanation

<.               Input < Output
 .;?             The list [Output, Input]
    {    }ᵐ      Map on [Output, Input]:
     ḋ             Prime decomposition
      ḅ            Group into sublists of consecutive equal elements
       lᵐ          Take the length of each sublist
           =∧    The result of the map must be the same for the Output and the Input
\$\endgroup\$
4
\$\begingroup\$

Python 2, 176 179 171 170 169 bytes

  • Added three bytes as the question changed from set of exponents to list of exponents; set(f) was changed to sorted(f).
  • Saved eight bytes thanks to ovs; golfing the if / else block down to multiplication.
  • Saved a byte; golfed (n!=r) to (n>r).
  • Saved a byte; golfed while N>1 to while~-N.
N=input();n=-~N
def F(N):
 r,f=0,[]
 while~-N:
	for n in range(2,-~N):
	 if N%n<1:f+=[1]*(n>r);f[-1]+=n==r;r=n;N/=n;break
 return sorted(f)
while F(N)!=F(n):n+=1
print n

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Haskell, 107 bytes

import Data.List
import Data.Numbers.Primes
p=sort.map(1<$).group.primeFactors
f x=until((==p x).p)(+1)$x+1

Try it online! Usage example: f 2500 yields 2704.

Thanks to nimi for pointing out a flaw and saving a bunch of bytes.


Without primeFactors build-in (117 bytes)

import Data.List
1%n=[]
x%n|0<-mod x n=n:div x n%n|m<-n+1=x%m
p=sort.map(1<$).group.(%2)
f x=until((==p x).p)(+1)$x+1

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python - 141 bytes

def s(n):
 i=1;d={}
 while n-1:
  i+=1
  if n%i<1:d[i]=d.get(i,0)+1;n/=i;i=1
 return d.values()
a=input()
j=a+1
while s(a)!=s(j):j+=1
print j
\$\endgroup\$
  • \$\begingroup\$ Your program seems to output the wrong value for 2500 as an input; 4624 instead of 2704. \$\endgroup\$ – Jonathan Frech Oct 2 '17 at 9:40
  • \$\begingroup\$ while n-1: can be while~-n:. \$\endgroup\$ – Jonathan Frech Oct 2 '17 at 9:42
2
\$\begingroup\$

05AB1E, 15 bytes

XµN‚εÓ0K{}ËNI›&

Try it online!

Explanation

Xµ                # Loop over N in [0 ...] until 1 match is found
  N‚              # pair N with input
    ε    }        # apply to each
     Ó            # list prime exponents
      0K          # remove zeroes
        {         # sort
          Ë       # check that they are equal
              &   # and
           NI›    # that N is greater than the input
\$\endgroup\$
1
\$\begingroup\$

Python 3 + Sympy, 118 bytes

from sympy.ntheory import*
f=lambda k:sorted(factorint(k).values())
g=lambda i,k=2:i<k and f(k)==f(i)and k or g(i,k+1)

Try it online!

\$\endgroup\$

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.