A while ago, I had a look at the prime factorization of 27000:

27000 = 23 × 33 × 53

There are two special things about that:

  • consecutive-prime: The primes are consecutive: 2 is the 1st prime, 3 is the 2nd prime, 5 is the 3rd prime.
  • constant-exponent: The exponent is the same for every prime (always 3)

Mathematically expressed:

An integer x is a consecutive-prime/constant-exponent number if there exist strictly positive integers n, k, m such that x = pnm × pn+1m × ... × pn+km, where pj is the j-th prime

Your task is to test if a positive integer fulfills these conditions.

Input:

A positive integer > 1, in any reasonable form.

Output:

One of two values, at least one of which has to be constant, indicating whether the input is a consecutive-prime/constant-exponent number.

Edge cases:

  • primes are truthy, as the factorization for prime p is p1
  • other numbers that can be written as pm where p is a prime are also truthy.

Rules:

  • Standard loopholes apply.
  • No worries about integer overflow, but numbers up to 255 must work.
  • Shortest code in bytes wins.

Test cases:

Truthy:

2
3
4
5
6
7
8
9
11
13
15
27000
456533

Falsy:

10
12
14
72
10000000

Here is a python script generating some test cases.

The fact that I accepted an answer does not mean that the challenge is over; the winner can still change!

  • You could probably come at this the other way by generating a list of all such numbers and checking if the input is in the list – Engineer Toast May 16 at 15:48
  • @EngineerToast There are infinitely many truthy numbers though. – Alexis Olson May 16 at 21:58
  • @AlexisOlson Sure, but a finite that can be handled as integers by many languages. – Engineer Toast May 16 at 22:11
  • Your mathematical expression has Pj doesn't relate to the x = Pn^m part. I'm assuming you meant Pn is the n-th prime – Veskah May 16 at 22:37
  • @Veskah n has a specific value (index of the first prime dividing x), so saying Pn is the n-th prime is awkward if you also want to imply that Pn+1 is the n+1-th prime. – Dennis May 17 at 3:53

16 Answers 16

up vote 12 down vote accepted

05AB1E, 4 bytes

Ó0ÛË

Try it online!

Explanation

Ó     # get a list of prime exponents
 0Û   # remove leading zeroes
   Ë  # all remaining elements are equal
  • ÎÓKË is all I can think of other than this, nice one... I was thinking ß but it does the opposite of what I thought. – Magic Octopus Urn May 18 at 1:53

CJam, 30 29 bytes

{mFz~)-!\__W=,\0=>\-:mp1#W=&}

Try it online!

My first answer after a nearly 2(!)-year break, so it can probably be golfed more. This is a block that takes input as an integer (can also be mapped over for arrays of integers).

Explanation

{        e# Begin block
 mF      e# Factor input, giving an array of primes and their powers
 z~      e# Transpose and dump, giving an array of primes and an array of powers
 )-      e# Check that the powers are the same: subtract each power from the last element
 !       e# Negate to make sure they're all 0
 \__W=,  e# Get the range from 0 to the largest prime minus one
 \0=>    e# Slice that array so it only includes everything larger than the smallest prime
 \-      e# Remove the original primes from the range array
 :mp     e# Check each element for primality. If the input's primes are consecutive,
         e# this will contain no primes
 1#W=    e# Make sure a "1" is not found
 &       e# If the powers are the same AND primes are consecutive, return 1. Otherwise, 0.
}

Jelly, 13 6 5 bytes

ÆEt0E

Try it online!

Still outgolfed... (thanks Erik for -1 byte)


Explanation

ÆE     # get a list of prime exponents (noooo long builtin name)
  t0   # remove zeroes on both sides (leading or trailing)
    E  # all remaining elements are equal

JavaScript (ES6), 87 84 bytes

Returns 0 for truthy or a non-zero integer for falsy.

f=(n,k=2,j,i)=>n%k?j*(P=d=>k%--d?P(d):d==!i)(k)|j-i|(n>1&&f(n,k+1,i)):f(n/k,k,j,-~i)

Try it online!

Commented

f = (                     // f() = recursive function taking:
  n,                      //   n = input
  k = 2,                  //   k = current factor
  j,                      //   j = reference exponent, initially undefined
  i                       //   i = current exponent, undefined each time we start testing
) =>                      //       the next factor
  n % k ?                 // if k is not a divisor of n:
    j * (                 //   ignore the primality of k if j is still undefined
      P = d =>            //     P() = function testing if k is prime:
        k % --d ?         //       decrement d; if d is not a divisor of k:
          P(d)            //         do a recursive call until it is
        :                 //       else:
          d == !i         //         unless i is already defined: d must not be equal to 1
                          //         (if it is: k is the next prime but does not divide n)
    )(k) |                //   initial call to P() with d = k
    j - i | (             //   if both i and j are defined, they must be equal
      n > 1 &&            //   if n is not yet equal to 1,
      f(n, k + 1, i)      //   go on with k + 1 and j = i
    )                     //   (otherwise, stop recursion and return what we have)
  :                       // else:
    f(n / k, k, j, -~i)   //   increment the current exponent and go on with n / k

Stax, 5 6 bytes

╣♥qJ╬c

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

|n    get the exponents of the prime factorization
0:D   trim leading zeroes
:u    array has exactly a single distinct element

Edit: This doesn't work on 512. I'll give it some thought and hopefully a fix later. It works now.

Stax, 9 bytes

1 is truthy, 0 is falsy

αAG<└\{┬⌠

Run and debug it

Explanation

|nX0-u%x:^=      # Full Program, unpacked, implicit input
|n               # Exponents of sequential primes in factorization. (eg. 20 -> [2 0 1])
  X              # Save to X register
   0-            # Remove all '0' from array
     u%          # Get unique numbers and get length of array
       x         # Copy back the array saved to X
        :^       # Is it ascending
         =       # Are the two comparisons equal? implicit output

Can probably be golfed more, but it covers the cases I was missing in the last solution.

MATL, 12 11 10 bytes

YFtgYsg)Zs

Try it at MATL Online!

Thanks to Luis Mendo for the remove-leading-zeroes part. He also pointed out that swapping truth values is allowed, so this returns 0 for numbers that satisfy the challenge requirements and any positive value otherwise.

Grosso Modo, this generates the exponents of the sequential prime factorization, removes leading zeroes and calculates the standard deviation.

  • I think 0iYFhdz works for 7 bytes: prepend a 0 to the exponents of the sequential factorization, consecutive differences, number of non-zeros. The result is 1 iff input satisfies the requirement – Luis Mendo May 18 at 10:48
  • @LuisMendo Sorry for the delayed response, but you can post that as a separate answer. It is most definitely very different. – Mr. Xcoder May 20 at 7:04
  • OK, I posted it as an answer – Luis Mendo May 20 at 12:39

J, 16 bytes

Big thanks to FrownyFrog for -8 bytes!

(=&#+/\=@#])_&q:

Try it online!

My old solution:

J, 24 bytes

[:(1=[:#@~.{.@I.}.])_&q:

Try it online!

Explanation:

_&q: prime exponents

{.@I.}.] removes the leading zeros by finding the first non-zero element:

     }.   drop
       ]  from the list of exponents
{.@       as much items as the first of the 
   I.     indices of non-zero elements

1=[:#@~. tests if all remaining numbers are equal:

  [:#@~.  finds the length of the list after removing the duplicates
1=        is it 1?

Husk, 11 bytes

Λ§*≈¤≈oṗ←gp

Try it online!

Outputs 0 if not a consecutive-prime/constant-exponent number.

MATL, 7 bytes

0iYFhdz

The result is 1 iff input satisfies the requirement.

Try it online! Or verify all test cases

Explanation

0    % Push 0
i    % Push input number
YF   % Exponents of consecutive prime factors
h    % Concatenate horizontally
d    % Consecutive differences
z    % Number of nonzeros. Implicitly display

Java 10, 223 191 178 176 bytes

n->{var s=new java.util.HashSet();for(int f=1,i=1,x,j;n>1;){for(x=++i,j=2;j<x;)x=x%j++<1?1:x;if(x>1){j=0;if(n%i<1)for(f=0;n%i<1&n>0;n/=i)j++;if(f<1)s.add(j);}}return s.size();}

Returns 1 as truthy, and >=2 as falsey.

Try it online.

Explanation:

n->{                   // Method with integer parameter and boolean return-type
  var s=new java.util.HashSet();
                       //  Set to keep track of the prime exponents
  for(int f=1,         //  Prime-flag, starting at 1
          i=1,x,j;     //  Index and temp integers
          n>1;){       //  Loop as long as `n` is still larger than 1
    for(x=++i,         //   Set `x` to `i`, after we've increased `i` by 1 first with `++i`
        j=2;           //   Set `j` to 2 (first prime)
        j<x;)          //   Inner loop as long as `j` is still smaller than `x`
      x=x%j++<1?       //    If `x` is divisible by `j`:
         1             //     Set `x` to 1
        :              //    Else:
         x;            //     Leave `x` unchanged
    if(x>1){           //    If `x` is larger than 1 (if `i` is a prime):
      j=0;             //     Use `j` as counter, and set it to 0
      if(n%i<1)        //     If `n` is divisible by `i`:
        for(f=0;       //      Set `f` to 0
            n%i<1      //      And loop as long as `n` is still divisible by `i`,
            &n>0;      //      and `n` is larger than 0
          n/=i)        //       Divide `n` by `i`
          j++;         //       And increase `j` by 1
      if(f<1)          //     If the flag `f` is now/still 0:
        s.add(j);}}    //      Add counter `j` to the Set
  return s.size();}    //  Return the amount of items in the Set
                       //  (1 being true, >=2 being false)

Some example inputs:

n=15:

  • Flag remains 1 for the first prime 2 (because 15 is not divisible by 2).
  • Flag goes from 1 to 0 as soon as we're at the prime 3. Since 15 is divisible by 3, n becomes 5 (15/31), and the Set becomes [] → [1].
  • Then we check the next prime 5. Since 5 is divisible by 5, n becomes 1 (5/51), and the Set remains the same ([1] → [1]).
  • Now n=1, so we stop the outer loop. The Set ([1]) only contains one item, the 1 from both adjacent primes 3 and 5, so we return true.

n=14:

  • Flag goes from 1 to 0 for the first prime 2 (because 14 is divisible by 2). n becomes 7 (14/21), and the Set becomes [] → [1].
  • Then we check the next prime 3. Since 7 is not divisible by 3, n remains the same, and the Set becomes [1] → [1,0].
  • Then we check the next prime 5. Since 7 is also not divisible by 5, n remains the same, and the Set remains the same as well ([1,0] → [1,0]).
  • Then we check the next prime 7. Since 7 is divisible by 7, n becomes 1 (7/71), and the Set remains the same ([1,0] → [1,0]).
  • Now n=1, so we stop the outer loop. The Set ([1,0]) contains two items, the 1 from the non-adjacent primes 2 and 7, and the 0 from the primes 3 and 5, so we return false.

n=72:

  • Flag goes from 1 to 0 for the first prime 2, because 72 is divisible by 2 (multiple times). So n becomes 9 (72/23), and the Set becomes [] → [3].
  • Then we check the next prime 3. Since 9 is divisible by 3 (multiple times), n becomes 1 (9/32), and the Set becomes [3] → [3,2].
  • Now n=1, so we stop the outer loop. The Set ([3,2]) contains two items, the 3 from prime 2, and the 2 from prime 3, so we return false.
  • 1
    You can remove <2 and return an int (specify that you return 1 for truthy). – wastl May 20 at 18:37
  • @wastl Ah, missed the rule about only one of the two values being consistent. In that case 1 is truthy and 2 or higher is falsey. Thanks. – Kevin Cruijssen May 20 at 20:27

Octave, 67 bytes

@(x)~any(diff(find(h=histc(factor(x),primes(x))))-1)&h(h>0)==max(h)

Try it online!

I believe this is the only solution that uses a histogram.

Explanation:

This makes a histogram, where the variable to be counted are the factors of the input, and placed in the bins primes(x), which is all primes less than the input. We then find the location of the prime factors, takes the difference between each of the indices and subtract one. If there are any elements that aren't zero (i.e. the difference of the indices of prime numbers is not 1), then this will result in a falsy value, otherwise it will return a truthy value.

We then chech that all non-zero elements in the histogram are equal to the maximum element. If there are values that aren't equal then this will result in a falsy value, otherwise it will return a truthy value.

If both those blocks are truthy then our input is a consecutive prime constant exponent number!

Wolfram Language (Mathematica), 65 bytes

Differences[{PrimePi@#,#2}&@@@FactorInteger@#]~MatchQ~{{1,0}...}&

Try it online!

Pari/GP, 63 bytes

n->#Set(vector(#(a=factor(n)~),i,[primepi(a[1,i])-i,a[2,i]]))<2

Try it online!

J, 14 bytes

1#.2~:/\0,_&q:

1 in the output indicates consecutive constant exponent.

Try it online!

        0,_&q:   zero followed by the prime exponents of input
   2~:/\         for every two consecutive values, 1 if they are different
1#.              convert from base-1, just add them up

Clean, 127 bytes

import StdEnv
@n=[]== $n
?n#j= $n
= @n||j==filter@[hd j..last j]&&any(\p=(prod j)^p==n)[1..n]
$n=[i\\i<-[2..n-1]|n/i*i==n&& @i]

Try it online!

Defines the function ? :: Int -> Bool using $ :: Int -> [Int] to factorize and @ :: Int -> Bool to check primality.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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