Dense Number Sequence

Question

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

• Beta Decay: So many prime number sequences... I didn't know so many existed
• Adnan: @βετѧΛєҫαγ There are also primes called Sexy Primes ( ͡° ͜ʖ ͡°).
• R. Kap: What is the maximum value for n?
• user45941: @R.Kap As high as your language of choice can go.

Answer 1

Jelly, 9 bytes

ÆE2Sḍ2μ#Ṫ

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

How it works

ÆE2Sḍ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.
 2 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.

Answer 2

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

• Jo King: Divisible by 2 can just be less than 3
• Razetime: for some reason, <3 still requires an extra increment → at the end, maintaining the same byte count. @JoKing
• Jo King: ah, i guess <3 includes 1, which throws off the indexing

Answer 3

Vyxal 3, 13 bytes

kNʎ℗n∆qk±≡∨}i

Vyxal It Online!

kNʎ℗n∆qk±≡∨}i­⁡​‎‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌­
 i # ‎⁡index implicit input into
kN # ‎⁢natural numbers
 ʎ } # ‎⁣filtered by
 ℗ # ‎⁤is it prime
 ∨ # ‎⁢⁡or
 n∆q # ‎⁢⁢are its prime exponents
 k±≡ # ‎⁢⁣exactly equal to [1, 1]?
💎

Created with the help of Luminespire.

<script type="vyxal3">
kNʎ℗n∆qk±≡∨}i
</script>
<script>
 args=[["5"],["15"],["102"]]
</script>
<script src="https://themoonisacheese.github.io/snippeterpreter/snippet.js" type="module"/>

• Weird Glyphs: dense(102) =194? I think you have some false positives... Found one, dense(5) = 8, because it has four factors :) It can maybe work if you remove the cubes
• Themoonisacheese: @WeirdGlyphs d'oh! i always get tripped up by powers of 2. fixed for 1 byte.

Answer 4

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
 Q1⁄2 # if equal increase counter

Try it online

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

Vyxal rG, 56 bits^v2 , 7 bytes

λ∆ǐ2∑2Ḋ;ȯ

Try it Online!

port of jelly

Answer 9

PARI/GP, 45 bytes

Simple iteration.

k->n=1;while(k,numdiv(n++)-2*omega(n)||k--);n

If you don't mind using the deprecated & for the shortcut AND operator && you can also do

k->n=1;while(k,numdiv(n++)==2*omega(n)&k--);n

Answer 10

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

• R. Kap: Can't you use the += operator to save 2 bytes?
• user5957401: 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.

Answer 11

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.

Answer 12

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!