12
\$\begingroup\$

OEIS: A167171

A dense number is a number that has exactly as many prime divisors as non-prime divisors (including 1 and itself as divisors). Equivalently, it is either a prime or a product of two distinct primes. The first 100 dense numbers are:

2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 67, 69, 71, 73, 74, 77, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 103, 106, 107, 109, 111, 113, 115, 118, 119, 122, 123, 127, 129, 131, 133, 134, 137, 139, 141, 142, 143, 145, 146, 149, 151, 155, 157, 158, 159, 161, 163, 166, 167, 173, 177, 178, 179, 181, 183, 185, 187, 191, 193, 194

Given a nonnegative integer n, output dense(n). n may be 0-indexed or 1-indexed.

Reference implementation (Sage)

import itertools

def dense_numbers():
    n = 1
    while True:
        prime_divisors = [x for x in divisors(n) if x.is_prime()]
        non_prime_divisors = [x for x in divisors(n) if not x.is_prime()]
        if len(prime_divisors) == len(non_prime_divisors):
            yield n
        n += 1

N = 20

print itertools.islice(dense_numbers(), N, N+1).next()

Try it online

\$\endgroup\$
  • \$\begingroup\$ So many prime number sequences... I didn't know so many existed \$\endgroup\$ – Beta Decay Aug 15 '16 at 20:37
  • 2
    \$\begingroup\$ @βετѧΛєҫαγ There are also primes called Sexy Primes ( ͡° ͜ʖ ͡°). \$\endgroup\$ – Adnan Aug 15 '16 at 20:39
  • \$\begingroup\$ @Adnan Oh myy ;D \$\endgroup\$ – Beta Decay Aug 15 '16 at 20:40
  • \$\begingroup\$ What is the maximum value for n? \$\endgroup\$ – R. Kap Aug 16 '16 at 17:18
  • \$\begingroup\$ @R.Kap As high as your language of choice can go. \$\endgroup\$ – Mego Aug 16 '16 at 18:13
3
\$\begingroup\$

Jelly, 9 bytes

ÆE²Sḍ2µ#Ṫ

Reads from STDIN and uses 1-based indexing. Try it online!

How it works

ÆE²Sḍ2µ#Ṫ  Main link. No arguments. Implicit argument: 0

      µ#   Read an integer n from STDIN and execute the chain to the left for
           k = 0, 1, 2, ... until n of them return a truthy value.
           Return the array of matches.
ÆE           Compute the exponents of k's prime factorization.
  ²          Square each exponent.
   S         Compute the sum of all squares.
    ḍ2       Test if 2 is divisible by the result (true iff  the sum is 1 or 2).
        Ṫ  Tail; extract the last (n-th) matching value of k.
\$\endgroup\$
2
\$\begingroup\$

Actually, 12 bytes

All credits to Dennis for his algorithm.

`w♂N;*2%Y`╓N

Try it online!

`w♂N;*2%Y`╓N

`        `     define a function
 w             prime factorization in exponent form:
               18 = (2^1)*(3^2) becomes [[2,1],[3,2]]
  ♂N           get the last element (exponent) of each sublist
    ;*         dot-product with self; equivalent to squaring
               each item and then taking the sum
      2%Y      test divisibility by 2
          ╓    first (input) solutions to the above function
           N   get the last element.
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 12 11 bytes

1-indexed

µ             # while counter != input
 NÑ           # get divisors of current number
   p          # check if prime
    D         # duplicate
     O        # sum one copy
      s_O     # invert and sum the other copy
         Q½   # if equal increase counter

Try it online

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

Brachylog, 17 bytes

:1yt.
1<.=$p#dl<3

Try it online!

Predicate 0 (main predicate)

:1yt.
:1y     Find the first (input) solutions of predicate 1
   t    Last element
    .   Unify with output

Predicate 1 (auxiliary predicate)

1<.=$p#dl<3
1<.            1 < output
  .=           assign a value to output
  . $p#d       output's prime factorization contains no duplicate
        l      and the length
         <3    is less than three
\$\endgroup\$
0
\$\begingroup\$

R, 93 Bytes

dense=function(n){a=b=0;for(i in which(!n%%1:n))if(which(!i%%2:i)+1==i)a=a+1 else b=b+1;a==b}

It has a tendency to throw a warning. Its not really a problem. Allowing the warning saves me 5 bytes.

Ungolfed

dense=function(n){
     a=b=0                                #Initializing
     factors = which(!n%%1:n)             #Finds all factors
     for(i in factors)                    #Loops through factors
         prime = which(!i%%2:i)+1==i      #Tests if current factor is prime. If it is -- the first term in this vector will be TRUE. Otherwise, it will be false.
           if (prime) a=a+1 else b=b+1    #If first term is true, add 1 to a. Else add one to b. 
      return(a==b)                        #Test equality of a and b.
}
\$\endgroup\$
  • \$\begingroup\$ Can't you use the += operator to save 2 bytes? \$\endgroup\$ – R. Kap Aug 16 '16 at 17:21
  • \$\begingroup\$ Sadly, R doesn't have any useful incrementation operators like += or a++. Sometimes there can be shorter ways (taking advantage of loop structure mostly), but I don't know of one here. \$\endgroup\$ – user5957401 Aug 16 '16 at 17:41
0
\$\begingroup\$

Python, 79 bytes

f=lambda n,k=2:n<1or-~f(n-(sum((k%i<1)+2*(k%i**2<1)for i in range(2,k))<3),k+1)

Uses 1-based indexing. Test it on Ideone.

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

PHP, 118 Bytes

for($i=1;!$o=$s[$argn];$r[2]?:$t+=2*$$i=1,$t?:$s[]=$i)for($t=0,$r=[],$n=++$i;$n;$n--)$i%$n?:$t+=${$r[]=$n}?:-1;echo$o;

Try it online!

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

Axiom, 102 bytes

f(n:PI):PI==(i:=1;repeat(i:=i+1;a:=divisors(i);2*#[x for x in a|prime?(x)]=#a=>(n=1=>break;n:=n-1));i)

ungolf and result

-- 1 base Indexed: return the n_th number i that has 2*#divisorsPrimeOf(i)=#divisors(i)
ff(n:PI):PI==
     i:=1
     repeat
        i:=i+1
        a:=divisors(i)
        2*#[x for x in a|prime?(x)]=#a=>(n=1=>break;n:=n-1)
     i

(3) -> [f(i)  for i in 1..23]
   (3)  [2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,31,33,34,35,37,38]
                                               Type: List PositiveInteger
\$\endgroup\$

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.