# Numbers with similar powers

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

• Just for reference, this is A081761 in the OEIS. Oct 1, 2017 at 20:43

# 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.


# Mathematica, 61 bytes

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


Try it online!

-4 bytes from @Misha Lavrov

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

# Pyth, 15 bytes

fqFmShMrPd8,QTh


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


# Jelly, 15 14 bytes

1 byte thanks to Erik the Outgolfer.

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


Try it online!

# 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


# Python 2, 176179171170 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!

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!

# 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

• Your program seems to output the wrong value for 2500 as an input; 4624 instead of 2704. Oct 2, 2017 at 9:40
• while n-1: can be while~-n:. Oct 2, 2017 at 9:42

# 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


# 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!

# J, 32 bytes

>:@]^:(1--:&(_&q:/:[email protected]:))^:_>:


Try it online!

Start from input + 1 >: and keep incrementing while the list of prime factors _&q: minus any zeros -.0:, then sorted /:~@, does not match 1--:.

# Ruby, 69 bytes

g=->m{m.prime_division.map{_2}.sort}
->n{((n+1)..).find{g[_1]==g[n]}}


Attempt This Online!

# Japt, 20 bytes

Hideous! But I can't think of a better way :\

@[UX]Ëk ü mÊñÃre}aUÄ


Try it