13
\$\begingroup\$

Let \$n\$ be some positive integer. We say that \$n\$ is of even kind if the prime factorisation of \$n\$ (counting duplicates) has an even number of integers. For example, \$6 = 2 \times 3\$ is of even kind. Likewise, we say \$n\$ is of odd kind of the prime factorisation of \$n\$ has an odd number of integers, such as \$18 = 2 \times 3 \times 3\$. Note that as the prime factorisation of \$1\$ contains \$0\$ primes, it is of even kind.

Let \$E(n)\$ be the count of positive integers of even kind less than or equal to \$n\$, and \$O(n)\$ be the count of positive integers of odd kind less than or equal to \$n\$. For example, for \$n = 14\$, we have

  • \$E(14) = 6\$ (\$1, 4, 6, 9, 10, 14\$), and
  • \$O(14) = 8\$ (\$2, 3, 5, 7, 8, 11, 12, 13\$)

You are to write a program which takes some positive integer \$n \ge 1\$ as input, and outputs the two values \$E(n)\$ and \$O(n)\$. You may input and output in any convenient method, and you may output the two outputs in any format that consistently presents the values (e.g. you cannot output one in unary and another in decimal), and that clearly distinguishes between the two (typically, has some kind of obvious delimiter).

This is a challenge, so the shortest code in bytes wins.

Test cases

n -> [E(n), O(n)]
1 -> [1, 0]
2 -> [1, 1]
3 -> [1, 2]
4 -> [2, 2]
5 -> [2, 3]
6 -> [3, 3]
7 -> [3, 4]
8 -> [3, 5]
9 -> [4, 5]
10 -> [5, 5]
11 -> [5, 6]
12 -> [5, 7]
13 -> [5, 8]
14 -> [6, 8]
15 -> [7, 8]
16 -> [8, 8]
17 -> [8, 9]
18 -> [8, 10]
19 -> [8, 11]
20 -> [8, 12]
\$\endgroup\$
5
  • \$\begingroup\$ Diamond coated brownie points for beating/matching my 7 byte Jelly answer \$\endgroup\$ Commented Oct 21, 2022 at 1:17
  • 5
    \$\begingroup\$ Trivia: Polya conjecture states that E(n) <= O(n) for all n >= 2. This conjecture was proven to be false, with the smallest counterexample being n = 906,150,257. \$\endgroup\$
    – Bubbler
    Commented Oct 21, 2022 at 7:43
  • \$\begingroup\$ @cairdcoinheringaahing Can we return only one value for 1? The Japt answer does that but I don't feel like it's right (even though that would make things simpler for me) \$\endgroup\$
    – Fatalize
    Commented Oct 21, 2022 at 14:22
  • \$\begingroup\$ @Fatalize No, you must return a 1 and a 0. If, however, you are outputting only unary, then outputting an empty string is okay (as that's 0 in unary), but otherwise, there should be two clear values output. \$\endgroup\$ Commented Oct 21, 2022 at 15:09
  • 3
    \$\begingroup\$ Trivia on the trivia: Pólya never conjectured "Pólya's conjecture" (more accurately called "Pólya's problem")—instead he showed that it would imply the Riemann Hypothesis if it were true. \$\endgroup\$ Commented Oct 22, 2022 at 2:31

22 Answers 22

6
\$\begingroup\$

J, 19 bytes

(-,])1#.2|1#@q:@+i.

Try it online!

  • 1...+i. 1 2 ... n
  • #@q: Length # of prime factors q: of each
  • 1#.2| Sum of even lengths
  • (-,]) Input minus that sum - catted with , that sum ]
\$\endgroup\$
5
\$\begingroup\$

Jelly, 8 bytes

RÆE§ḂSṄạ

Try it online!

RÆE§ḂSṄạ
R         - Range [1, input]
 ÆE       - For each, get a list of the prime exponents
   §      - Sum each
    Ḃ     - Modulo each by 2
     S    - Sum
      Ṅ   - Print (with a trailing newline)
       ạ  - Get the absolute difference between this and the input (also implicitly printed)
\$\endgroup\$
1
  • \$\begingroup\$ Nice! You can still remove a byte tho :P \$\endgroup\$ Commented Oct 21, 2022 at 1:46
4
\$\begingroup\$

PARI/GP, 31 bytes

n->sum(i=1,n,I^(bigomega(i)%2))

Attempt This Online!

Outputs a complex number where the real part is \$E(n)\$ and the imaginary part is \$O(n)\$.

\$\endgroup\$
4
\$\begingroup\$

05AB1E, 8 7 bytes

LÓOÉ1Ý¢

Try it online or verify all test cases.

Explanation:

-1 byte by realizing that: amount of prime factors of \$x\$ == sum(exponents of \$x\$'s prime factorization): see that they are the same here.

L        # Push a list in the range [1, (implicit) input]
 Ò       # Get the prime exponents of each inner integer
  O      # Sum each inner list together
   É     # Check for each sum whether it's odd
    1Ý   # Push pair [0,1]
      ¢  # Count the occurrences of 0 and 1 in the list
         # (after which the result is output implicitly)
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Tounge-in-cheek, but since the question explicitly mentioned the possibility of unary output: 5 bytes with unary output of zero-digits for E(n) and one-digits for O(n)... \$\endgroup\$ Commented Oct 21, 2022 at 11:16
  • \$\begingroup\$ @DominicvanEssen Nice bending of the rules. :D \$\endgroup\$ Commented Oct 21, 2022 at 11:19
4
\$\begingroup\$

JavaScript (ES6), 71 bytes

f=(n,a=[0,0])=>n?f(n-1,a,a[(g=_=>k>n?0:n%k?g(k++):1^g(n/=k))(k=2)]++):a

Try it online!

Commented

f = (                 // f is a recursive function taking:
  n,                  //   n = input
  a = [0, 0]          //   a[] = output array
) =>                  //
n ?                   // if n is not equal to 0:
  f(                  //   do a recursive call:
    n - 1,            //     decrement n
    a,                //     pass a[]
    a[                //     update a[]:
      ( g =           //       g is a recursive function
        _ =>          //       which ignores its parameter
        k > n ?       //       if k is greater than n:
          0           //         stop the recursion
        :             //       else:
          n % k ?     //         if k is not a divisor of n:
            g(k++)    //           increment k and do a recursive call
          :           //         else:
            1 ^       //           invert the result
            g(n /= k) //           divide n by k and do a recursive call
      )(k = 2)        //       initial call to g, starting with k = 2
    ]++               //     increment a[0] or a[1], depending on the
                      //     parity of the number of prime divisors of n
  )                   //   end of recursive call
:                     // else:
  a                   //   return a[]
\$\endgroup\$
4
\$\begingroup\$

Desmos, 101 97 bytes

f(K)=∑_{k=1}^Kmod([1,0]+∑_{n=2}^klog_n(gcd(n^{ceil(log_nk)},k))sign(∏_{a=3}^nmod(n,a-1)),2)

Output is the list \$[E(n),O(n)]\$. It will fail on larger values due to floating point inaccuracies, but I've tested values such as \$1000\$ and it gives the right output, so it's pretty much a nonissue.

Try It On Desmos!

Try It On Desmos! - Prettified

A shorter version of the above code technically works, but it fails for values greater than \$15\$ due to floating point errors (so it doesn't even pass all the test cases):

88 84 bytes

f(K)=∑_{k=1}^Kmod([1,0]+∑_{n=2}^klog_n(gcd(n^k,k))sign(∏_{a=3}^nmod(n,a-1)),2)

Try It On Desmos!

Try It On Desmos! - Prettified

\$\endgroup\$
3
\$\begingroup\$

Vyxal o, 8 bytes

ɾǐvL∷∑…ε

Try it Online!

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 8 bytes

'ǐ₂;L~ε"

Try it Online!

A flagless 8 byter that uses a method that is a little different to the other answer.

7 bytes using this approach with a flag:

Vyxal o, 7 bytes

'ǐ₂;L…ε

Try it Online!

\$\endgroup\$
3
\$\begingroup\$

Ruby, 72 66 bytes

-6 bytes thanks to Dingus

->n{[e=(1..n).map{|m|m.prime_division.sum{_2}}.count{_1%2<1},n-e]}

Attempt This Online!

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

Factor + math.primes.factors, 58 50 bytes

[ dup [1,b] [ factors length odd? ] count tuck - ]

Try it online!

  • dup Create an extra copy of the input.
  • [1,b] Create a range from one to the input (inclusive).
  • [ ... ] count Count the number of elements in the range for which [ ... ] returns true.
  • factors length odd? Does it have an odd number of factors?
  • tuck - Subtract the result from the input non-destructively. (Implicit multiple return)
\$\endgroup\$
3
\$\begingroup\$

Japt, 12 bytes

Had to sacrifice 2 bytes to handle 1 :\

2Æõk è_ʤ̦X

Try it

2Æõk è_ʤ̦X     :Implicit input of integer U
2Æ               :Map each X in the range [0,2)
  õ              :  Range [1,U]
   k             :  Prime factors of each
     è           :  Count the elements that return true
      _          :  When passed through the following function
       Ê         :    Length
        ¤        :    To binary string
         Ì       :    Last character
          ¦X     :    Not equal to X?
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 40 bytes

Length/@PrimeOmega@Range@#~GroupBy~OddQ&

View it on Wolfram Cloud!

Output in the form <|False->E(n),True->O(n)|>.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ For n=1, outputs just <|False->1|>. \$\endgroup\$
    – Bubbler
    Commented Oct 21, 2022 at 8:09
  • \$\begingroup\$ As noted by Bubbler, the output format doesn't work for n = 1, as it should include both E(n) and O(n) \$\endgroup\$ Commented Oct 21, 2022 at 11:41
2
\$\begingroup\$

R, 79 bytes

\(n)c(y<-sum(sapply(1:n,f<-\(n,p=2)sum(x<-!n%%p,if(n>1)f(n/p^x,p+!x))%%2)),n-y)

Attempt This Online!

Returns O(n), E(n).

Helper function f returns the number of prime factors, f%%2 returns whether-or-not this is odd: f<-\(n,p=2)sum(x<-!n%%p,if(n>1)f(n/p^x,p+!x))

\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 63 bytes

.+
$*
M!&`.+
+%`^(2*(1+))\2+$
2$1
22|¶

O`2?1
(1)+(21)*
$#1 $#2

Try it online! Link is to test suite that outputs the results for 1..n. Explanation:

.+
$*

Convert to unary.

M!&`.+

List all the numbers from n down to 1.

+%`^(2*(1+))\2+$
2$1

Count the number of prime factors of each number, using repeated 2s as the count. This leaves a lone trailing 1 once all of the prime factors have been counted.

22|¶

Take the parity of the counts of prime factors, so that 1 means that it had an even number and 21 means that it had an odd number, and join all of the results together.

O`2?1

Sort the 1s and 21s separately to make them easier to count.

(1)+(21)*
$#1 $#2

Count the number of 1s and 21s.

\$\endgroup\$
2
\$\begingroup\$

GeoGebra, 66 bytes

InputBox(n
a=Sum(Zip(Mod(Length(PrimeFactors(a)),2),a,1...n
ai+n-a

Try It On GeoGebra!

Output is in the form \$E(n)+O(n)i\$.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 10 bytes

aBsm.&1lPh

Try it online!

Outputs [O(n), E(n)].

Explanation

aB            bifurcate the absolute difference of implicit eval(input()) and
  s           the sum of
   m          map over implicit range(eval(input()))
    .&1       modulo 2 (bitwise and 1)
       l      the length of 
        P     the list of the prime factors of
         h    1 + implicit map lambda variable
\$\endgroup\$
2
\$\begingroup\$

[Julia 1.1], 92 bytes

using Primes
~N=(X=map(n->sum([b for (a,b)=factor(n)]),1:N);[sum(X.%2 .==0),sum(isodd.(X))])

Julia 1.0 appears to be supported by the package Primes.jl, but I haven't been able to import it successfully. Here is the output in Julia 1.1:

julia> VERSION
v"1.1.1"

julia> using Primes

julia> ~N=(X=map(n->sum([b for (a,b)=factor(n)]),1:N);[sum(X.%2 .==0),sum(isodd.(X))])
~ (generic function with 1 method)

julia> map(x -> println(lpad(x,2) * " -> $(~x)"), 1:20);
 1 -> [1, 0]
 2 -> [1, 1]
 3 -> [1, 2]
 4 -> [2, 2]
 5 -> [2, 3]
 6 -> [3, 3]
 7 -> [3, 4]
 8 -> [3, 5]
 9 -> [4, 5]
10 -> [5, 5]
11 -> [5, 6]
12 -> [5, 7]
13 -> [5, 8]
14 -> [6, 8]
15 -> [7, 8]
16 -> [8, 8]
17 -> [8, 9]
18 -> [8, 10]
19 -> [8, 11]
20 -> [8, 12]

This solution could be adapted without Primes in Julia 0.4, when factor was still part of base Julia.

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

Brachylog, 15 bytes

⟦₁{ḋl%₂}ᵍlᵐĊ|;0

Try it online!

Explanation

4 additional bytes needed at the end to deal with the special case of 1.

⟦₁                  Range [1, ..., Input]
  {    }ᵍ           Group by:
   ḋl%₂                 Length of prime decomposition mod 2
         lᵐ         Map length
            Ċ|;0    Output must have 2 elements; otherwise (Input = 1), Output = [Input, 0]
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 40 bytes

F…·¹N«≔⁰θWΦι¬﹪ι⁺²λ«≧÷⁺²⌊κι≦¬θ»⊞υθ»IE²№υι

Try it online! Link is to verbose version of code. Explanation:

F…·¹N«

Loop from 1 up to and including n.

≔⁰θ

Assume even kind.

WΦι¬﹪ι⁺²λ«

While the current value has any nontrivial factors: ...

≧÷⁺²⌊κι

... divide it by the lowest such factor, and...

≦¬θ

... flip between even and odd kind.

»⊞υθ

Save the kindness of the current value.

»IE²№υι

Output the counts of even and odd kindness.

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

Ohm v2, 11 bytes

@€olé;ΣD³a«

Try it online!

Returns a list of [E(n), O(n)]. Note that Ohm v2 formats numbers a little weirdly when they are in a list, but they are definitely the right numbers.

Explained

@€olé;ΣD³a«
@            # Push a range from 1 to the input to the stack
 €   ;       # To each item in the range from before:
  ol         # Get the length of the full prime factorization of the item
    é        # and then push whether the length is even
      ΣD     # Push two copies of the sum of that list - the first copy is how many numbers are E(n), and the second will be used to calculate how many numbers are O(n)
        ³a   # Get the absolute difference of the input and the E(n) count
          «  # Pair into a list
\$\endgroup\$
1
\$\begingroup\$

Arturo, 52 bytes

$[n][x:∑map 1..n=>[%size factors.prime&2]@[n-x,x]]

Try it

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

Thunno, \$ 13 \log_{256}(96) \approx \$ 10.70 bytes

R1+Zh.S2%10dc

Attempt This Online! Port of Kevin Cruijssen's 05AB1E answer.

Thunno, \$ 16 \log_{256}(96) \approx \$ 13.17 bytes

DR1+Zh.S2%SDZKAD

Attempt This Online! Port of Steffan's Jelly answer.

Explanations

R1+Zh.S2%10dc  # Implicit input
R1+            # Push range(1, input + 1)
   Zh          # Prime factor exponents
     .S2%      # Sum mod 2 of each
         10dc  # Count 1s and 0s
DR1+Zh.S2%SDZKAD  # Implicit input
DR1+              # Duplicate and push range(1, input + 1)
    Zh            # Prime factor exponents
      .S2%        # Sum mod 2 of each
          SDZK    # Sum and print without popping
              AD  # Absolute difference with input
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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