# Dense Number Sequence

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

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

# 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.


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

# 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  # 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.  # Husk, 13 bytes !fö¦2ṁo□LgpN  Try it online! ## Explanation !fö¦2ṁo□LgpN N List of natural numbers fö filtered by the following 4 functions: gp prime factorization, grouped into equal runs ṁo□L get length of each run, square and sum ¦2 is 2 divisible by the sum? ! nth element in filtered list  • Divisible by 2 can just be less than 3 – Jo King Commented Oct 5, 2020 at 8:01 • for some reason, <3 still requires an extra increment → at the end, maintaining the same byte count. @JoKing Commented Oct 5, 2020 at 8:06 • ah, i guess <3 includes 1, which throws off the indexing – Jo King Commented Oct 5, 2020 at 8:14 # VyxalrG, 56 bitsv2, 7 bytes λ∆ǐ²∑2Ḋ;ȯ  Try it Online! port of jelly # 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. }  • Can't you use the += operator to save 2 bytes? Commented Aug 16, 2016 at 17:21 • 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. Commented Aug 16, 2016 at 17:41 # 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. # 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!

# 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
`