Enteros excesivos

18

Para un entero positivon con la factorización prima n = p1^e1 * p2^e2 * ... pk^ekdonde p1,...,pkson primos y e1,...,ekenteros positivos, podemos definir dos funciones:

  • Ω(n) = e1+e2+...+ekEl número de divisores primos (contados con multiplicidad) ( A001222 )
    • ω(n) = kEl número de divisores primos distintos. ( A001221 )

Con esas dos funciones definimos el exceso e(n) = Ω(n) - ω(n) ( A046660 ). Esto se puede considerar como una medida de qué tan cerca está un número de estar libre de cuadrados.

Desafío

Para un nretorno entero positivo dado e(n).

Ejemplos

Porque n = 12 = 2^2 * 3tenemos Ω(12) = 2+1y ω(12) = 2y por lo tanto e(12) = Ω(12) - ω(12) = 1. Para cualquier número nlibre de cuadrados que tengamos e(n) = 0. Los primeros términos son

1       0
2       0
3       0
4       1
5       0
6       0
7       0
8       2
9       1
10      0
11      0
12      1
13      0
14      0
15      0

Algunos detalles más en el wiki de OEIS.

falla
fuente
1
Quizás aclarar que eso ^es poder
Luis Mendo
55
Esto no es necesario en mi opinión. Este símbolo se usa aquí y en todo Internet, así como en muchas calculadoras y en muchos lenguajes de programación.
flawr

Respuestas:

7

MATL , 7 5 bytes

Yfd~s

Pruébalo en línea! O verificar todos los casos de prueba .

Explicación

Yf    % Implicit input. Obtain prime factors, sorted and with repetitions
d     % Consecutive differences
~     % Logical negate: zeros become 1, nonzeros become 0
s     % Sum. Implicit display
Luis Mendo
fuente
No sabía cómo factorfunciona en MATL, realmente genial =)
error
@flawr ¿Quiere decir YF(en la versión de 7 bytes del código) o Yf(5 bytes)? Este último es como en MATLAB
Luis Mendo
1
La función para los exponentes, el byte 5 ahora es aún más inteligente =)
error
6

Brachylog , 11 bytes

$pPd:Pr:la-

Pruébalo en línea!

Explicación

$pP            P is the list of prime factors of the Input
  Pd           Remove all duplicates in P
    :Pr        Construct the list [P, P minus duplicates]
       :la     Apply "length" to the two elements of that list
          -    Output is the subtraction of the first element by the second one
Fatalizar
fuente
6

Mathematica, 23 bytes

PrimeOmega@#-PrimeNu@#&

Muy aburrido. FactorIntegerya ocupa 13 bytes, y no puedo ver mucho de lo que se puede hacer con los 10 restantes.

u54112
fuente
4

Jalea , 5 bytes

ÆfI¬S

Pruébalo en línea!

Verifique todos los casos de prueba.

La respuesta del puerto de Luis Mendo en MATL .

ÆfI¬S

Æf     Implicit input. Obtain prime factors, sorted and with repetitions
  I    Consecutive differences
   ¬   Logical negate: zeros become 1, nonzeros become 0
    S  Sum. Implicit display
Monja permeable
fuente
Para el enfoque anterior, ÆF’SṪhabría funcionado, creo
Sp3000
@ Sp3000 Deberías publicar eso
Leaky Nun
@LeakyNun Estaba intentando portarlo yo mismo, pero la definición de ¬confundirme. No sabía que estaba vectorizado
Luis Mendo
@LuisMendo De hecho, los documentos de Jelly son desordenados.
Leaky Nun
3

05AB1E , 6 bytes

Òg¹fg-

Explicación

Òg      # number of prime factors with duplicates
     -  # minus
  ¹fg   # number of prime factors without duplicates

Pruébalo en línea!

Emigna
fuente
3

J 11 10 bytes

Guardado 1 byte gracias a Jonás .

1#.1-~:@q:
alephalpha
fuente
1
1#.1-~:@q:por 10 bytes. Buena idea usando ~:BTW.
Jonás
2

C, 74 bytes

f(n,e,r,i){r=0;for(i=2;n>1;i++,r+=e?e-1:e)for(e=0;n%i<1;e++)n/=i;return r;}

Ideone it!

Monja permeable
fuente
2

Python 2, 57 56 bytes

f=lambda n,k=2:n/k and[f(n,k+1),(n/k%k<1)+f(n/k)][n%k<1]

¡Gracias a @JonathanAllan por jugar golf en 1 byte!

Pruébalo en Ideone .

Dennis
fuente
Ah bien - puede ahorrar un byte utilizandon/k%k<1
Jonathan Allan
Correcto, n ya es divisible por k en ese punto. ¡Gracias!
Dennis
2

Haskell, 65 bytes

(c%x)n|x>n=c|mod n x>0=c%(x+1)$n|y<-div n x=(c+0^mod y x)%x$y
0%2
Damien
fuente
si esa es una función: ¿quién es la variable de entrada? quien es la salida gracias ...
RosLuP
(%) toma 3 variables de entrada: un acumulador (c), un número entero (x) y un número entero (n). Devuelve el exceso de (n) cuando c se establece en 0 yx en 2. Entonces (0% 2) es una función parcial que toma ny devuelve su exceso
Damien
1

Python 2, 100 99 98 96 bytes

n=input()
i=2
f=[]
while i<n:
 if n%i:i+=1
 else:n/=i;f+=i,
if-~n:f+=n,
print len(f)-len(set(f))

La mayor parte del código está ocupado por una versión de golf de esta respuesta SO , que almacena los factores primos de la entrada f. Luego, simplemente usamos la manipulación de conjuntos para calcular los factores en exceso.

¡Gracias a Leaky Nun por guardar 1 3 bytes!

Cobre
fuente
1

SILOS , 113 bytes

readIO
t=2
lbla
e=0
GOTO b
lblc
i/t
e+1
lblb
m=i
m%t
n=1
n-m
if n c
d=e
d/d
e-d
r+e
A=i
A-1
t+1
if A a
printInt r

Pruébalo en línea!

Un puerto de mi respuesta en C .

Monja permeable
fuente
Tan cerca de vencer a C :(
Rohan Jhunjhunwala
1

Javascript (ES6), 53 51 46 bytes

e=(n,i=2)=>i<n?n%i?e(n,i+1):e(n/=i,i)+!(n%i):0

Guardado 5 bytes gracias a Neil

Ejemplo:

e=(n,i=2)=>i<n?n%i?e(n,i+1):e(n/=i,i)+!(n%i):0

// computing e(n) for n in [1, 30]
for(var n = 1, list = []; n <= 30; n++) {
  list.push(e(n));
}
console.log(list.join(','));

Arnauld
fuente
1
Puede guardar 5 bytes mediante el cálculo rde forma recursiva: f=(n,i=2)=>i<n?n%i?f(n,i+1):f(n/=i,i)+!(n%i):0.
Neil
1

Bash, 77 bytes

IFS=$'\n '
f=(`factor $1`)
g=(`uniq<<<"${f[*]}"`)
echo $((${#f[*]}-${#g[*]}))

Programa completo, con entrada en $1 y salida a stdout.

Empezamos IFScon una nueva línea, para que la expansión "${f[*]}"esté separada por una nueva línea. Utilizamos la sustitución aritmética para imprimir la diferencia entre el número de palabras en la factorización con el resultado del filtrado uniq. El número en sí mismo se imprime como un prefijo por factor, pero también está presente después del filtrado, por lo que cae en la resta.

Toby Speight
fuente
0

Python, (con sympy) 66 bytes

import sympy;lambda n:sum(x-1for x in sympy.factorint(n).values())

sympy.factorintdevuelve un diccionario con factores como claves y sus multiplicidades como valores, entonces la suma de los valores es Ω(n)y el número de valores es ω(n), entonces la suma de los valores decrementados es lo que queremos.

Jonathan Allan
fuente
0

CJam, 11 bytes

ri_mf,\mF,-

Pruébalo en línea!

Explicación

ri_         Get an integer from input and duplicate it
   mf,      Get the number of prime factors (with repetition)
      \     Swap top 2 elements on the stack
       mF,  Get the number of prime factors (with exponents)
          - Subtract
Gato de negocios
fuente
0

C, 158

#define G(a,b) if(a)goto b
#define R return
f(n,i,j,o,w){if(!n)R 0;o=w=i=j=0;a:i+=2;b:if(n%i==0){++j;G(n/=i,b);}o+=!!j;w+=j;i+=(i==2);j=0;G(i*i<n,a);R w-o;}

Al principio está la instrucción goto ... incluso si es más larga que la suya, es más legible y correcta [si no considero que sea demasiado grande ...] un Idioma que tiene 10000 funciones de biblioteca es más que un Idioma que con pocas, 20 o 30 funciones de biblioteca pueden funcionar mejor [porque no podemos recordar todas estas funciones]

#define F for
#define P printf

main(i,r)
{F(i=0; i<100; ++i)
   r=f(i,0,0,0,0),P("[%u|%u]",i,r);
 R  0;
}

/*
 158
 [0|0][1|0][2|0][3|0][4|1][5|0][6|0][7|0][8|2]
 [9|0][10|0][11|0][12|1][13|0][14|0][15|0][16|3]
 [17|0][18|0][19|0][20|1][21|0][22|0][23|0][24|2][25|1][26|0][27|0] [28|1]
 [29|0][30|0][31|0][32|4][33|0][34|0][35|0][36|1]
 [37|0][38|0][39|0][40|2][41|0]
 */
RosLuP
fuente
0

GNU sed + coreutils, 55 bytes

(incluido +1 para -rbandera)

s/^/factor /e
s/ ([^ ]+)(( \1)*)/\2/g
s/[^ ]//g
y/ /1/

Entrada en decimal, en stdin; salida en unario, en stdout.

Explicación

#!/bin/sed -rf

# factor the number
s/^/factor /e
# remove first of each number repeated 0 or more times
s/ ([^ ]+)(( \1)*)/\2/g
# count just the spaces
s/[^ ]//g
y/ /1/
Toby Speight
fuente
0

APL (NARS) 35 caracteres, 70 bytes

{⍵=1:0⋄k-⍨+/+/¨{w=⍵⊃v}¨⍳k←≢v←∪w←π⍵}

la función π encuentra la factorización en primo de su argumento; hay pocos que digan que parece claro, pero para mí realiza más operaciones (desde la factorización) que el mínimo ... el rango de caracteres de conteo está fuera de los idiomas de golf porque parece contar demasiado, pero menos que los idiomas de golf ... prueba:

  f←{⍵=1:0⋄k-⍨+/+/¨{w=⍵⊃v}¨⍳k←≢v←∪w←π⍵}
  f¨1..15
0 0 0 1 0 0 0 2 1 0 0 1 0 0 0 
RosLuP
fuente