11
\$\begingroup\$

We've had powerful numbers, yes, but what about highly powerful numbers?

Highly powerful numbers

Let \$n\$ be a positive integer in the form

$$n = p_1^{e_{p_1}(n)}p_2^{e_{p_2}(n)}\cdots p_k^{e_{p_k}(n)}$$

for distinct, increasing primes \$p_1, p_2, ..., p_k\$ and, where \$e_{p_i}(n)\$ is a positive integer for all \$i = 1, 2, ..., k\$. Note that we don't include zero exponents here.

Now, for such an \$n\$, define

$$\operatorname{prodexp}(n) = \begin{cases} 1, & n = 1 \\ \prod^k_{i=1} e_{p_i}(n), & n > 1\end{cases}$$

Such an \$n\$ is said to be highly powerful if, for all \$1 \le m < n\$, \$\operatorname{prodexp}(m) < \operatorname{prodexp}(n)\$.

For example, \$n = 8\$ is a highly powerful number as we have \$\operatorname{prodexp}(n) = 3\$ and

\$m\$ \$\operatorname{prodexp}(m)\$
\$1\$ \$1\$
\$2\$ \$1\$
\$3\$ \$1\$
\$4\$ \$2\$
\$5\$ \$1\$
\$6\$ \$1\$
\$7\$ \$1\$

All of which are strictly less than \$3 = \operatorname{prodexp}(8)\$. Whereas \$n = 7\$ is not highly powerful as \$\operatorname{prodexp}(7) = 1 < 2 = \operatorname{prodexp}(4)\$.

The first few highly powerful numbers are

1, 4, 8, 16, 32, 64, 128, 144, 216, 288, 432, 864, 1296, 1728, 2592

This is A005934 on OEIS.


This is a standard challenge. You may choose whether to

  • Take a positive integer \$n\$ and output the \$n\$th highly powerful number (you may choose between 0 and 1 indexing)
  • Take a positive integer \$n\$ and output the first \$n\$ highly powerful numbers
  • Output all highly powerful numbers indefinitely

This is a challenge, so the shortest answer in bytes in each language wins.

\$\endgroup\$
3
  • \$\begingroup\$ I have a 13 byte Jelly answer that outputs the first \$n\$. Brownie points for beating or tying this \$\endgroup\$ Aug 4, 2023 at 1:16
  • \$\begingroup\$ So in plain(er) English, \$\operatorname{prodexp}(n)\$ is the product of the nonzero exponents in the prime decomposition of \$n\$, correct? \$\endgroup\$
    – DLosc
    Aug 4, 2023 at 16:19
  • \$\begingroup\$ @DLosc Correct, yes \$\endgroup\$ Aug 4, 2023 at 19:35

12 Answers 12

6
\$\begingroup\$

Jelly, 11 bytes

1ÆEP$ÐṀḢ=Ɗ#

Try it online! Prints the first n numbers. -1 thanks to Jonathan Allan.

Brownie points acquired.

1           # Starting from 1
          # # Find the first n integers where...
 --------Ɗ  # Last three elements as a monad
        =   # Where the number equals
       Ḣ    # The first of
     ÐṀ     # The indicies of maximal elements by...
 ---$       # Last two elements as a monad...
   P        # Product of 
 ÆE         # Exponents of prime factorisation of the number.
\$\endgroup\$
3
  • 2
    \$\begingroup\$ ÆEP$ saves one byte. This can be done since all-high-powerful-numbers have distinct prime factors that are a prefix of the primes. Proof by contradiction: assume there exists an all-high-powerful-number \$H=2^a 3^b 5^c \cdots p^0 (p+1)^n \cdots\$, this has an exponent-product of \$a b c \cdots n \cdots\$. The number \$C=2^a 3^b 5^c \cdots p^n \cdots\$ also has an exponent-product of \$a b c \cdots n \cdots\$ but \$C<H\$. \$\endgroup\$ Aug 4, 2023 at 19:58
  • \$\begingroup\$ * \$(p+1)\$ is meant to be the next prime after \$p\$ and \$a,b,c,n>0\$ if that is not clear. \$\endgroup\$ Aug 4, 2023 at 20:07
  • 1
    \$\begingroup\$ @JonathanAllan Neat! That can save a byte or two on the 05AB1E answer as well. \$\endgroup\$
    – emanresu A
    Aug 4, 2023 at 20:37
5
\$\begingroup\$

Vyxal, 9 bytes

ɾ‡∆ǐΠ∴=)ȯ

Try it Online! Outputs the first n highly powerful integers. -1 thanks to lyxal.

        ȯ # First n positive integers
-------)  # Where...
     ∴    # Maximum of...
ɾ         # Range from 1 to n
 ‡---     # By...
    Π     # Product of
  ∆ǐ      # Prime exponents
      =   # Is equal to the number?
\$\endgroup\$
4
  • \$\begingroup\$ Try it Online! for 9 bytes with the R flag \$\endgroup\$
    – lyxal
    Aug 4, 2023 at 2:59
  • \$\begingroup\$ @lyxal I know, I just didn't want to use it \$\endgroup\$
    – emanresu A
    Aug 4, 2023 at 3:00
  • \$\begingroup\$ Try it Online! for 9 bytes without a flag \$\endgroup\$
    – lyxal
    Aug 4, 2023 at 3:01
  • \$\begingroup\$ @lyxal Nice, I forgot ȯ can do that \$\endgroup\$
    – emanresu A
    Aug 4, 2023 at 3:05
4
\$\begingroup\$

05AB1E, 13 12 9 bytes

∞ʒDLÓPZk-

Outputs the infinite sequence.

-3 bytes thanks to @JonathanAllan.

Try it online.

Explanation:

∞          # Push an infinite list of positive integers: [1,2,3,...]
 ʒ         # Filter it by:
  D        #  Duplicate the current value
   L       #  Pop one, and push a list in the range [1,value]
    Ó      #  Get the exponents of each inner integer's prime factorizations
           #  (which will include 0s, but this doesn't matter for the results)
     P     #  Get the product of each inner list
      Z    #  Push the maximum (without popping the list)
       k   #  Pop the maximum and list, and push the first (0-based) index of this max
        -  #  Subtract this 0-based index from the duplicated current value
           #  (only 1 is truthy in 05AB1E)
           # (after which the filtered infinite list is output implicitly as result)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ No need to remove zeros, see my comments under emanresu A's Jelly answer \$\endgroup\$ Aug 4, 2023 at 21:07
  • 1
    \$\begingroup\$ @JonathanAllan Oh, thanks! I had tried replacing 0δK with some other things, like > or ! to deal with the zeroes, but I hadn't tried simply removing it completely 😅. Thanks for -3 bytes. \$\endgroup\$ Aug 5, 2023 at 10:43
3
\$\begingroup\$

PARI/GP, 60 bytes

p=n=0;while(1,if(p<q=vecprod(factor(n++)[,2]),p=q;print(n)))

Attempt This Online!

Outputs all highly powerful numbers indefinitely.


57 bytes but would stack overflow

f(p,n)=f(if(p<q=vecprod(factor(n++)[,2]),print(n);q,p),n)

Attempt This Online!

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

Nekomata, 9 bytes

Ňᵖ{Rƒᵐ∏Ɔ<

Attempt This Online!

Ňᵖ{Rƒᵐ∏Ɔ<
Ň           Any natural number
 ᵖ{         Check that:
   R          Range from 1 to the number
    ƒ         Factor each number
     ᵐ        Map:
      ∏         Take the product of exponents
       Ɔ<     Check that the last result is the largest
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 60 bytes

NθW‹Lυθ«→≔ⅈη≔¹ζ≔¹εW⊖η«≦⊕ε≔⌕⮌X⁰↨ηε⁰δ≧÷Xεδη¿δ≧×δζ»¿⬤υ›ζκ⊞υζ»Iⅈ

Try it online! Link is to verbose version of code. Eventually outputs the 1-indexed nth highly powerful number (avoid n>15 on TIO). Explanation:

Nθ

Input n.

W‹Lυθ«

Repeat until n record prime factorisation exponent product records have been found.

→≔ⅈη≔¹ζ≔¹ε

Increment the trial number and start to factorise it.

W⊖η«

Repeat until the trial number has been factorised.

≦⊕ε

Try the next potential factor.

≔⌕⮌X⁰↨ηε⁰δ

Find its multiplicity.

≧÷Xεδη

Divide the trial number by the prime power.

¿δ≧×δζ

Multiply the exponent product by the current exponent, if any.

»¿⬤υ›ζκ⊞υζ

If this is a record exponent product then save it.

»Iⅈ

Output the number with the nth record exponent product.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @JonathanAllan Sadly I test all potential factors, not just primes, so for instance for 30 I divide by 2, 3, 4 and 5. The division by 4 fails of course, but I can't record that as a zero, since 4 isn't prime. \$\endgroup\$
    – Neil
    Aug 5, 2023 at 0:12
3
\$\begingroup\$

JavaScript (Node.js), 70 bytes

Output all highly powerful numbers indefinitely, as suggested by @Arnauld.

for(x=p=0n;;p<s&&(p=s,console.log(x)))for(d=s=++x;d;)x%d+d--**x%x&&--s

Try it online!

JavaScript (Node.js), 72 bytes

Takes a positive integer \$ n \$ and returns the \$ n \$-th highly powerful number (1-indexed).

n=>eval('for(x=p=0n;n;p<s&&(p=s,n--))for(d=s=++x;d;x%d+d--**x%x&&--s)x')

Try it online!

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

Python3, 234 bytes

R=range
def P(n):
 d=[]
 while n>1:
  for i in R(2,n+1):
   if(i<3or all(i%j for j in R(2,i)))and 0==n%i:n//=i;d+=[i]
 r=1
 for i in{*d}:r*=d.count(i)
 return r
def f():
 n=0
 while(n:=n+1):
  if all(P(m)<P(n)for m in R(1,n)):print(n)

Try it online!

Prints the sequence indefinitely.

\$\endgroup\$
3
  • \$\begingroup\$ while n>1 could be just while n \$\endgroup\$ Aug 4, 2023 at 12:59
  • 1
    \$\begingroup\$ @BrianMinton Factorisation stops when n=1, not when n=0... \$\endgroup\$
    – Neil
    Aug 4, 2023 at 15:09
  • 1
    \$\begingroup\$ Although, while~-n would work, I think? \$\endgroup\$
    – Neil
    Aug 4, 2023 at 15:10
2
\$\begingroup\$

Pyth, 15 bytes

.fqh.M*FhMr8PZS

Try it online!

Outputs the first \$n\$ terms in the sequence.

Explanation

.fqh.M*FhMr8PZSZZQ    # implicitly add ZZQ
                      # implicitly assign Q = eval(input())
.f               Q    # Take the first Q items which are truthy over lambda Z
              SZ      #   range(1,Z+1)
    .M                #   filter this for elements which maximize lambda Z
            PZ        #     prime factors of Z
          r8          #     length encode
        hM            #     take just the lengths
      *F              #     reduce over multiplication
   h                  #   first element
  q             Z     #   is equal to Z
\$\endgroup\$
2
\$\begingroup\$

Gaia, 17 bytes

⟨┅⟨ḋ_v2%Π⟩¦ṅ¤⌉>⟩#

Try it online!

Returns the first (1-indexed) n all-high-powerful numbers.

There's a quirk with numeric mode where it returns a list [prime,exponent] for n<4 and for n>3 it returns a list [[prime1,exponent1],...]. I suppose that's what I get for golfing in a language that hasn't been updated in 6 years.

			; implicit input, n
⟨	       ⟩#	; find the first n positive integers where the following is truthy:
	   ṅ¤⌉>		; is the last element of the following list the unique maximum?
				; (literally, is the last element greater than the max of the remaining elements)
   ḋ_v2%Π  		; the product of the exponents in the prime factorization
 ┅⟨	 ⟩¦		; for each integer in the range 1..i (where i is the positive integer we're on now)
\$\endgroup\$
1
\$\begingroup\$

Ruby -rprime, 75 bytes

Prints infinitely.

p m=e=1
2.step{|x|d=x.prime_division.reduce(1){_1*_2[1]};m,e=p(x),d if d>e}

Attempt This Online! (50ms timeout)

# -rprime imports Prime as a command line flag
p m=e=1                 # Print 1 while also setting m (current most powerful)
                        #   and e (current highest exponent product)
2.step{|x|              # Count up infinitely starting from 2, store as x
  x.prime_division      # Get prime factors of x
   .reduce(1){_1*_2[1]} # Multiply the exponent component of each factor together
d=                      # Set that value as d
m,e=p(x),d if d>e       # if d > e, print x, set m to x, and set e to d
}                       # End loop structure
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 72 bytes

Try it online!

p=n=0;While[1<2,n++;q=Times@@Last/@FactorInteger[n];If[p<q,p=q;Print@n]]
\$\endgroup\$

Your Answer

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

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