Factor-poor numbers

Question

If a positive integer \$N > 2\$ has (strictly) less prime factors (without counting multiplicities) than its successor and its predecessor, we will call it a factor-poor number.

In other words, \$\omega(N) < \omega(N - 1)\$ and \$\omega(N) < \omega(N + 1)\$, where \$\omega(N)\$ is the number of unique prime factors of \$N\$.

Task

You can choose among the following I / O formats:

• Take an integer \$N\$ and output the \$N^{\text{th}}\$ factor-poor number. In case you choose this one, \$N\$ can either be 0 or 1 indexed.
• Take a positive integer \$N\$ and output the first \$N\$ factor-poor numbers.
• Print the sequence indefinitely.

---

You can take input and provide output through any standard method, in any programming language, while taking note that these loopholes are forbidden by default. This is code golf, so the shortest submission that abides to the rules wins.

I won't include separate test cases, because the methods of competing are different, but you can refer to the first 100 terms of this sequence, which is OEIS A101934:

11, 13, 19, 23, 25, 27, 29, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 131, 137, 139, 149, 151, 155, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 221, 223, 227, 229, 233, 239, 241, 243, 251, 259, 263, 265, 269, 271, 277, 281, 283, 289, 293, 307, 309, 311, 313, 317, 331, 337, 341, 343, 347, 349, 353, 359, 361, 365, 367, 371, 373, 379, 383, 389, 397, 401, 407, 409, 419, 421, 431, 433, 439, 441, 443

As an example, \$25\$ occurs in this sequence because \$\omega(25) = 1\$ (5), \$\omega(26) = 2\$ (2 and 13) and \$\omega(24) = 2\$ (2 and 3), so \$\omega(25) < \omega(24)\$ and \$\omega(25) < \omega(26)\$.

Answer 1

Brachylog, 21 bytes

⟨+₁≡-₁⟩{ḋdl}ᵐ⌋>~↰₂?ẉ⊥

Try it online!

Prints infinitely.

Explanation

⟨+₁≡-₁⟩                  Fork: The output of the fork is [Input + 1, Input -1]
       {   }ᵐ            Map:
        ḋdl                (predicate 2) the output is the length of the prime decomposition
                           of the input with no duplicates
             ⌋           Take the minimum result of that map
              >          This minimum is bigger than…
               ~↰₂?      …the output of predicate 2 with Input as input
                  ?ẉ     Write Input followed by a new line if that's the case
                    ⊥    False: backtrack and try another value for Input

Answer 2

Python 2, 123 119 bytes

q=lambda n:sum(n%i<all(i%j for j in range(2,i))for i in range(2,n+1))
i=2
while 1:
 i+=1
 if q(i-1)>q(i)<q(i+1):print i

Try it online!

Answer 3

Jelly, 13 12 bytes

Cr~ÆvÐṂN⁼Wø#

Prints the first n factor-poor numbers.

Try it online!

How it works

Cr~ÆvÐṂN⁼Wø#  Main link. No arguments.

          ø   Wrap the links to the left into a chain and begin a new chain.
           #  Read an integer n from STDIN and call the chain to the left with
              arguments k = 0, 1, 2, ... until n of them return a truthy value.
              Return those n values of k as an array.
C                 Complement; yield -k+1.
  ~               Bitwise NOT; yield -k-1.
 r                Range; yield [-k+1, -k, -k-1].
     ÐṂ           Yield those elements of [-k+1, -k, -k-1] for which the link to
                  the left returns the minimal value.
   Æv                 Count the number of unique prime factors.
                      Note that, for a negative argument, Æv counts -1 as well, and
                      0 is counted as a/the factor of 0. Negating the the arguments
                      eliminates the edge case 1 (no factors), which would be a
                      false positive otherwise.
                  For a factor-poor number, this yields [-k].
       N          Take the negatives of the resulting integers.
         W        Wrap; yield [k].
        ⁼         Test the results to both sides for equality.

Answer 4

MATL, 26 24 22 bytes

`T@3:q+YFg!sdZSd0>?@QD

Prints the sequence indefinitely.

Try it online!

Explanation

`         % Do...while loop
  T       %   Push true. Will be used as loop condition
  @       %   Push (1-based) iteration index, k 
  3:q     %   Push [1 2 3] minus 1, that is, [0 1 2]
  +       %   Add, element-wise. Gives [k k+1 k+2]
  YF      %   Exponents of prime-factor decomposition. Gives a 3-row matrix
  g       %   Convert to logical: non-zero numbers become 1
  !s      %   Transpose, sum of each column. Gives a row vector of 3 elements, 
          %   which are the number of unique prime factors of k, k+1 and k+2 
  d       %   Consecutive differences. Gives a row vector of 2 elements
  ZS      %   Sign: replaces each number by -1, 0 or 1
  d       %   Consecutive difference. Gives a single number
  0>      %   Is it positive?
  ?       %   If so
    @Q    %     Push k+1
    D     %     Display
          %   End (implicit)
          % End (implicit). The stack contains true, which (is consumed and)
          % causes an infinite loop

Answer 5

Husk, 22 bytes

f(ΠtSM<←ṙ1mȯLup§…←→)tN

Prints the sequence indefinitely, try it online or view the first N!

Alternatively §oΛ>←t could be used instead of ΠtSM<←.

Explanation

f(                  )tN  -- filter the tail of the naturals ([2,3…]) by:
  ΠtSM<←ṙ1m(Lup)§…←→     -- | takes a number as argument, example 11
                §…       -- | range of..
                  ←      -- | | the argument decremented (10)
                   →     -- | | to the argument incremented (12)
                         -- | : [10,11,12]
          m(   )         -- | map the following (example on 12) ..
              p          -- | | prime factors: [2,2,3]
             u           -- | | deduplicate: [2,3]
            L            -- | | length: 2
                         -- | : [2,1,2]
        ṙ1               -- | rotate by 1: [1,2,2]
    SM<                  -- | map the function (< X) over the list where X is ..
       ←                 -- | | the first element (1)
                         -- | : [0,1,1]
   t                     -- | tail: [1,1]
  Π                      -- | product: 1
                         -- : [11,13,19,23,25,27,29…

Answer 6

Pyth, 14 bytes

.f!-.ml{Pb}tZh

Try it here!

It was initially a suggestion on Dopapp's answer, but they told me to post it separately.

How it works?

.f!-.ml{Pb}tZh | Full program. Takes input from STDIN, outputs the first N to STDOUT.

.f             | (var: Z) Output the first N values which satisfy the predicate.
          }tZh | Creates the list [Z - 1, Z, Z + 1].
    .m         | (var: b) Take the elements with minimal function value.
        Pb     | Prime factors of b.
      l{       | Deduplicate, get length.
               | For a factor-poor number, this yields itself wrapped in a singleton.
   -           | Remove Z from that.
  !            | Logical negation.

Answer 7

Haskell, 105 86 bytes

Thanks to @Wheat Wizard, @Bruce Forte, and @Laikoni for saving 19 bytes.

[n|n<-[2..],d n<d(n-1),d n<d(n+1)] d x=[1|n<-[1..x],x`rem`n<1,all((>0).rem n)[2..n-1]]

Answer 8

Octave,  87   83  79 bytes

Thanks to @Cows quack for saving a byte and thanks to @Luis Mendo for saving three six bytes!

f=@(n)nnz(unique(factor(n)));n=9;while++n if[f(n-1) f(n+1)]>f(n)disp(n);end;end

Prints the sequence indefinitely.

Try it online!

73 bytes with leading n = before each value:

f=@(n)nnz(unique(factor(n)));n=9;while++n if[f(n-1) f(n+1)]>f(n)n end;end

Try it online!

Answer 9

05AB1E, 14 13 bytes

Outputs the nth factor-poor number (1-indexed)

µ3LN+Íf€gÀć›P

Try it online!

Explanation

µ                 # loop over N (1,2,3, ...) until counter equals input
 3L               # push the range [1,2,3]
   N+             # add current N
     Í            # subtract 2
      f           # get unique prime factors of each
       €g         # get length of each factor list
         À        # rotate left
          ć       # extract the head
           ›      # check if the remaining elements are strictly greater
            P     # product
                  # if 1, increment counter
                  # implicitly output final N

Answer 10

Pyth, 30 25 bytes

#=hTI&>l{PhTKl{PT>l{PtTKT

This is my first real Pyth golf, so any comments are very appreciated.

A big thanks to Xcoder!

Explanation

#                         | Loop until error
 =hT                      | Add one to T (initially 10)
    I&                    | If both...
      >l{PhTKl{PT         | The number of unique prime factors of T+1 is greater than that of T (store in K) 
                 >l{PtTK  | And the number of unique prime factors of T-1 is greater than K (from before)
                        T | Then implicitly print T

TIO.

Answer 11

JavaScript (ES6), 94 bytes

Returns the Nth factor-poor number, 0-indexed.

f=(i,n=9)=>(P=(n,i=k=1)=>++k>n?0:n%k?P(n,1):i+P(n/k--,0))(n)>P(++n)&P(n)<P(n+1)&&!i--?n:f(i,n)

Try it online!

How?

We first define the P() function which returns the number of unique prime factors of a given integer.

P = (                   // P = recursive function taking:
  n,                    //   n = input number to test
  i =                   //   i = flag to increment the number of prime factors
  k = 1                 //   k = current divisor
) =>                    //
  ++k > n ?             // increment k; if k is greater than n:
    0                   //   stop recursion
  :                     // else:
    n % k ?             //   if k is not a divisor of n:
      P(n, 1)           //     do a recursive call with n unchanged and i = 1
    :                   //   else:
      i +               //     add i and
      P(n / k--, 0)     //     do a recursive call with n / k and i = 0; decrement k

The wrapping code now reads as:

f = (                   // given:
  i,                    //   i = input index
  n = 9                 //   n = counter
) =>                    //
  P(n) > P(++n) &       // increment n; if P(n - 1) is greater than P(n)
  P(n) < P(n + 1) &&    // and P(n) is less than P(n + 1)
  !i-- ?                // and we have reached the correct index:
    n                   //   return n
  :                     // else:
    f(i, n)             //   go on with the next value

Answer 12

Japt, 29 27 26 bytes

Not entirely happy with this but at least it's better than my first attempt which was over 40 bytes!

Outputs the Nth number in the sequence, 1-indexed.

È=Jõ_+X k â ÊÃé)e>Xo)«´U}a

Try it

---

Explanation

Implicit input of integer U.

È                       }a

Return the first integer X that returns true when passed through the following function.

=Jõ             )

Assign the array [-1,0,1] to X.

 _+X      Ã

Pass each element of that array through a function which firstly adds the current value of X.

k â Ê

Get the length (Ê) of the unique (â) prime factors (k) of the result.

é

Rotate the resulting array one to the right.

e>Xo)

Pop (o) the last element from X and check if all remaining elements are greater than it.

«´U

If so, decrement U and check if it is equal to 0.

Answer 13

Python 3, 97 bytes

n,g=9,lambda m,k=2,p=1:m//k and(m%k<p%k)+g(m,k+1,p*k*k)
while 1:n+=1;g(n-1)>g(n)<g(n+1)!=print(n)

In theory, this prints the sequence indefinitely. In practice, g eventually exceeds the recursion limit.

Try it online!

Answer 14

C (gcc), 126 bytes

j,t;o(n){for(j=t=0;j++<n;)if(n%j<1)for(t--;j>1>n%j;)n/=j;t=~t;}
m(J){for(J=3;;J++)if(o(J-1)>o(J)&o(J)<o(J+1))printf("%d,",J);}

Try it online!

Answer 15

APL NARS, 124 bytes, 62 chars

{(⍵>1E4)∨⍵≤0:¯1⋄x←9+⍳10×⍵⋄⍵↑(∊{v←⍴∘∪∘π¨⍵+2-⍳3⋄2=+/v>2⌷v}¨x)/x}

It should return answer until 1E4, then return -1 error; it suppose 9..10xargument has enought right numbers; test:

  z←{(⍵>1E4)∨⍵≤0:¯1⋄x←9+⍳10×⍵⋄⍵↑(∊{v←⍴∘∪∘π¨⍵+2-⍳3⋄2=+/v>2⌷v}¨x)/x}  
  z 0
¯1
  z 1
11 
  z 20
11 13 19 23 25 27 29 37 41 43 47 49 53 59 61 64 67 71 73 79 

Answer 16

Clean, 130 123 117 bytes

import StdEnv
?n=[1\\q<-[p\\p<-[2..n]|and[gcd p i<2\\i<-[2..p-1]]]|n rem q<1]
f=[n\\n<-[3..]| ?n<min(?(n-1))(?(n+1))]

Equates to an infinite number of terms of the sequence. Since it's all nested comprehensions, it can't take advantage of graph reduction very well and so is quite slow, even for such a bad algorithm.

Try it online!