Numbers with similar powers

Question

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 2² x 5¹. The smallest integer greater than p with identical exponents in its prime factorization is q = 28 = 2² x 7¹.

The prime factorization of p = 2500 is 2² x 5⁴. The smallest integer greater than p with identical exponents in its prime factorization is q = 2704 = 2⁴ x 13².

Rules

The input is guaranteed to be an integer greater than 1.
This is code-golf, 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

\$\begingroup\$ Just for reference, this is A081761 in the OEIS. \$\endgroup\$
– Jonathan Frech
Oct 1, 2017 at 20:43 — Jonathan Frech, Oct 1, 2017 at 20:43

Community · Accepted Answer · 2020-06-17 09:04:33Z

10

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 1, 2017 at 18:52

H.PWiz

11.6k2 gold badges20 silver badges56 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

6

Mathematica, 61 bytes

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

Try it online!

-4 bytes from @Misha Lavrov

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 1, 2017 at 18:39

ZaMoC

24.4k2 gold badges29 silver badges79 bronze badges

\$\begingroup\$ A more concise way of writing such a While loop is s=#;While[f@++s!=f@#];s. \$\endgroup\$
– Misha Lavrov
Oct 1, 2017 at 21:45
1

\$\begingroup\$ You can replace f[x_] with f@x_ to save a byte. \$\endgroup\$
– numbermaniac
Oct 2, 2017 at 0:12
1

\$\begingroup\$ Or even go the composition-salad route of defining f=Last/@#&@*FactorInteger/*Sort. \$\endgroup\$
– Misha Lavrov
Oct 2, 2017 at 2:23

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Leaky Nun · Accepted Answer · 2017-10-01 20:30:58Z

5

Jelly, 15 14 bytes

1 byte thanks to Erik the Outgolfer.

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

Try it online!

edited Oct 1, 2017 at 20:30

answered Oct 1, 2017 at 18:24

Leaky Nun

49.6k6 gold badges107 silver badges281 bronze badges

\$\begingroup\$ It took you almost 3 minutes. ;) \$\endgroup\$
– Arnauld
Oct 1, 2017 at 18:26
1

\$\begingroup\$ -1 byte by using 2#Ṫ instead \$\endgroup\$
– Erik the Outgolfer
Oct 1, 2017 at 18:59

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

5

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 2, 2017 at 6:55

Fatalize

38.4k5 gold badges67 silver badges160 bronze badges

Add a comment |

Jonathan Frech · Accepted Answer · 2017-10-02 18:25:23Z

5

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!

edited Oct 2, 2017 at 18:25

answered Oct 1, 2017 at 19:02

Jonathan Frech

7,3411 gold badge21 silver badges43 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 1, 2017 at 22:28

Laikoni

26.1k6 gold badges51 silver badges115 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

2

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 2, 2017 at 0:07

Maltysen

25.7k4 gold badges54 silver badges127 bronze badges

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

Add a comment |

Emigna · Accepted Answer · 2017-10-02 07:14:41Z

2

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

answered Oct 2, 2017 at 7:14

Emigna

52.9k5 gold badges42 silver badges162 bronze badges

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-10-01 20:58:52Z

1

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!

answered Oct 1, 2017 at 20:58

Mr. Xcoder

42.3k9 gold badges79 silver badges214 bronze badges

Add a comment |

Jonah · Accepted Answer · 2020-05-17 18:14:52Z

1

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

answered May 17, 2020 at 18:14

Jonah

33k4 gold badges38 silver badges92 bronze badges

Add a comment |

Jordan · Accepted Answer · 2022-12-06 21:44:32Z

1

Ruby, 69 bytes

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

Attempt This Online!

answered Dec 6, 2022 at 21:44

Jordan

9,7261 gold badge30 silver badges47 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2022-12-07 16:10:07Z

1

Japt, 20 bytes

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

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

Try it

answered Dec 7, 2022 at 16:10

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Stack Exchange Network

Numbers with similar powers

Examples

Rules

Test cases

13 Answers 13

Husk, 10 bytes

Explantion

Mathematica, 61 bytes

Pyth, 15 bytes

How does this work?

Alternatives

Jelly, 15 14 bytes

Brachylog, 13 bytes

Explanation

Python 2, 176 179 171 170 169 bytes

Haskell, 107 bytes

Without `primeFactors` build-in (117 bytes)

Python - 141 bytes

05AB1E, 15 bytes

Python 3 + Sympy, 118 bytes

J, 32 bytes

Ruby, 69 bytes

Japt, 20 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
primes
permutations
or ask your own question.

Hot Network Questions

Numbers with similar powers

Examples

Rules

Test cases

13 Answers 13

Husk, 10 bytes

Explantion

Mathematica, 61 bytes

Pyth, 15 bytes

How does this work?

Alternatives

Jelly, 15 14 bytes

Brachylog, 13 bytes

Explanation

Python 2, 176 179 171 170 169 bytes

Haskell, 107 bytes

Without primeFactors build-in (117 bytes)

Python - 141 bytes

05AB1E, 15 bytes

Python 3 + Sympy, 118 bytes

J, 32 bytes

Ruby, 69 bytes

Japt, 20 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfprimespermutations or ask your own question.

Related

Hot Network Questions

Without `primeFactors` build-in (117 bytes)

Not the answer you're looking for? Browse other questions tagged
code-golf
primes
permutations
or ask your own question.