20
\$\begingroup\$

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)\$.

\$\endgroup\$
  • \$\begingroup\$ Can I output a leading n = before each value? \$\endgroup\$ – Steadybox Jan 3 '18 at 12:29
  • \$\begingroup\$ @Steadybox Sketchy, but I'll allow it :-/ \$\endgroup\$ – Mr. Xcoder Jan 3 '18 at 12:30
  • \$\begingroup\$ I added it as an alternative version. \$\endgroup\$ – Steadybox Jan 3 '18 at 12:31

16 Answers 16

7
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ @FryAmTheEggman thanks! Even that I didn't used your suggestion, it inspired me on another approach that saved 4 bytes :D \$\endgroup\$ – Rod Jan 3 '18 at 17:50
  • \$\begingroup\$ Nice! I was sure there was a way to avoid two ugly lambdas :) \$\endgroup\$ – FryAmTheEggman Jan 3 '18 at 17:56
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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…
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ when using rem ==0 and /=0 can be relaced with <1 and >0 respectively. \$\endgroup\$ – Sriotchilism O'Zaic Jan 3 '18 at 22:14
  • \$\begingroup\$ There is no need for a let, defining d as auxiliary function is fine (see the guide to golfing rules). Also sum can be omitted, the comparison works the same on lists. 86 bytes: Try it online! \$\endgroup\$ – Laikoni Jan 4 '18 at 4:26
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I think the function f can become f=@(n)length(unique(factor(n))) for one less byte. \$\endgroup\$ – Cows quack Jan 3 '18 at 12:25
2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ I was just about t suggest switching to µ, so I guess I am just going to point out my alternative – N<N>Ÿ can substitute 3LN+Í, if that helps. \$\endgroup\$ – Mr. Xcoder Jan 3 '18 at 13:45
  • \$\begingroup\$ @Mr.Xcoder: Similarily, ®XŸN+ also works. Or 0®X)N+ in which case À would not be needed. Unfortunately they all end up at the same byte count. \$\endgroup\$ – Emigna Jan 3 '18 at 13:58
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 14 bytes: .f!-.ml{Pb}tZh (prints the first n) (.f retrieves the first n values that satisfy a condition over [1,2,3,...] and uses a variable Z, }tZh generates the integer range [Z - 1 ... Z + 1], .m return the list of elements with minimal function value (with b), l{Pb gets the count of distinct divisors, - discards Z from the list, ! applies logical negation) \$\endgroup\$ – Mr. Xcoder Jan 3 '18 at 14:12
  • 1
    \$\begingroup\$ @Mr.Xcoder, wow I don't think I would have gotten that anytime soon! Wouldn't you say it merits its own answer? \$\endgroup\$ – Daniel Jan 3 '18 at 14:18
  • \$\begingroup\$ @Dopapp Ok then, I posted it separately. +1 Welcome to Pyth golfing! \$\endgroup\$ – Mr. Xcoder Jan 3 '18 at 14:20
  • \$\begingroup\$ 25 bytes using your approach. \$\endgroup\$ – Mr. Xcoder Jan 3 '18 at 14:29
  • \$\begingroup\$ Nope. h is +1, t is -1, while K is a variable which gets assigned without =. For example, K4 assigns K to 4. You can then access it using K. \$\endgroup\$ – Mr. Xcoder Jan 3 '18 at 14:32
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

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

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!

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

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 
\$\endgroup\$
  • 4
    \$\begingroup\$ about 150 bytes? \$\endgroup\$ – Shaggy Jan 3 '18 at 20:04
  • \$\begingroup\$ @Shaggy yes it was one approximate value; but +- it is right for the golfed one... \$\endgroup\$ – RosLuP Jan 4 '18 at 6:50
  • \$\begingroup\$ By my count the score here is 147 bytes, not 152 (number of characters is irrelevant). Further reading: codegolf.meta.stackexchange.com/q/9428/58974 \$\endgroup\$ – Shaggy Jan 4 '18 at 11:03
  • \$\begingroup\$ @Shaggy the number 152 would be the size in bytes of one file that contain only that code (copy past, save that code in a notepad (Window) document and observe "property " of that file ) \$\endgroup\$ – RosLuP Jan 4 '18 at 15:24
  • \$\begingroup\$ That's not how we count bytes here. \$\endgroup\$ – Shaggy Jan 5 '18 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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