The Nineteenth Byte

Leaky Nun

11:00 PM

Alright, so it is on OEIS again.

Why am I not surprised.

Should I post it on main?

Rohan Jhunjhunwala

Has anyone just exploited OEIS for lots of rep?

Like just posting a random sequence from OEIS with no justification?

Leaky Nun

You may try.

Rohan Jhunjhunwala

It seems a bit underhanded-cheaty

Just a free way to get rep

Or a quick way to be downvoted

Leaky Nun

The fact that the sequence appears in OEIS does not affect in any way whether the sequence itself is interesting enough to be posted on main.

Rohan Jhunjhunwala

I agree

But like if you pick a random sequence with no justification

Seems like perfect hnq bait

Leaky Nun

11:06 PM

The fact that the sequence appears in OEIS does not affect in any way whether the sequence itself is interesting enough to be posted on main.

Sp3000

@LeakyNun Currently out, will have to test later. Not sure how much faster your optimisations are exactly, still looks mainly on the same order of trial division (over primes)?

Leaky Nun

If you post an uninteresting sequence or a hard sequence then you will either get downvoted or have no answers.

Rohan Jhunjhunwala

Ok, that makes sense

Sp3000

Interesting inclusion of isqrt though, almost surprised Python doesn't have that

Leaky Nun

@Sp3000 sieve is on the same order of trial division?

I dont know, it improved quite a lot for me

because addition should be much faster than division

Sp3000

11:09 PM

@LeakyNun The problem is is_prime defaults to trial division if it divides none of the primes in the sieve

Leaky Nun

the old version was test each number and append independently

since array appending should be quite costly

@Sp3000 oh, will fix that later

I just heavily optimized the other functions

the prime count is so optimized now

Sp3000

tbh the part I'm confused about is why a sieve is being used for is_prime rather than a primality testing (or composite testing) algorithm

Leaky Nun

heh, I told myself I would not mess with those algorithms

Sp3000

Oh.. er... okay? Any particular reason out of curiosity?

Leaky Nun

because they are too complicated

I may do it later

Sp3000

11:16 PM

Er... I see

Leaky Nun

@Sp3000 how did you come up with n^3*n?

Sp3000

OEIS, haven't proven because I need to head off soon

Leaky Nun

How did you find that OEIS?

Rohan Jhunjhunwala

Sieve should be significantly faster than trial division iff you are trying to generate many prime numbers

Leaky Nun

seconded

Rohan Jhunjhunwala

11:19 PM

(Learnt that from Project Euler)

There is no way to succeed at a "generate the billionth prime" type question without such an algorithm.

Leaky Nun

I dont think you can generate the billionth prime by sieve

unless you have like a billion bits of memory

Rohan Jhunjhunwala

Sorry,

Billionth meant to be an illustrative example

Of generating a large number of primes

DJMcMayhem

@LeakyNun you can store a large prime in one bit? That's awesome!

Leaky Nun

@DJMcMayhem yes

and think twice before you laugh at me

Rohan Jhunjhunwala

@DJMcMayhem we're using this compression scheme
https://1.bp.blogspot.com/-mQr2LHIF6fM/Vrae4WGmMGI/AAAAAAAAA8s/7hpffR5FbUg/s320/fitbit.png

2

Citation to Conor O Brien of course

Leaky Nun

11:33 PM

well not really one bit

maybe like 1X bits for one prime

depends on the prime gaps

Downgoat

cheddar> 'asdafasdfas'.smallcaps
"ᴀsᴅᴀғᴀsᴅғᴀs"

@ConorO'Brien ^

Rohan Jhunjhunwala

But in all reality say we are storing 64 bit unsined long types

Leaky Nun

@Downgoat what the hell

Rohan Jhunjhunwala

\o/ \o/ \o/

what a useful feature

Leaky Nun

@RohanJhunjhunwala no i'm storing bitstring

where each prime is exactly the bit '1'

Downgoat

11:34 PM

@RohanJhunjhunwala ¯\_(ツ)_/¯ it was in the STDLIB suggestions

Rohan Jhunjhunwala

@Downgoat my remark was only fifty percent sarcastic (ok more like 80%-100%), but thats hilarious. Too bad you cant use it for the small caps question :(

@LeakyNun ok

Leaky Nun

whatever, i'm out

Rohan Jhunjhunwala

@LeakyNun 64 billion bits is "only" 8 gigabytes

it could be stored (with enough heap space and ram)

Downgoat

question: shuold i have substitution regex literals in cheddar?

Rohan Jhunjhunwala

yes

"String Literal".replaceAll("regex or string literal","substitution");

Downgoat

11:38 PM

@RohanJhunjhunwala that exists all ready

I mean like:

"goat".sub(s/oa/ao/) -> gaot

Rohan Jhunjhunwala

sure I guess

Its golifier

Downgoat

> .wipe() method for objects of class Ass

ಠ_ಠ

Rohan Jhunjhunwala

:D

Downgoat

question: is there a compression algo that will correctly decompress even if i chop the decomperssed string in half?

(I want to store first million digits of PI but i dont want t o waste space)

Rohan Jhunjhunwala

I'm not sure what u want?

ColdGolf

11:46 PM

Hello!

Rohan Jhunjhunwala

But from what I understand I hope that question is a joke

Ninjad by coldgolf

:(

ColdGolf

??

Downgoat

e.g. 123abc -> åß∂ç but åß -> 123

Rohan Jhunjhunwala

So I was typing a comment, and your comment got in between the comment I was responding to @ColdGolf

@Downgoat yes this very effective compression algorithm ... en.wikipedia.org/wiki/Null_encryption

@Downgoat but in all seriousness, like a run length decoding algorithm would do it.

ColdGolf

So, if there are any mods here, [my post](http://codegolf.stackexchange.com/questions/90391/repetition-of-letters) was marked as a duplicate of something not similar at all to it.

First of all, what the so-called "duplicate" post considers to be input, it's actually the *output* in my challenge. It's completely reversed.

Secondly, the format of the input I user, is nothing related to what the other poster used. The challenges are also different anyways, so it's not like I just changed the formats and that's it.

Downgoat

11:49 PM

@ColdGolf I think you're going under the idea that duplicate challenges are the exact same

Rohan Jhunjhunwala

sorry @ColdGolf it is clearly a dupe. The input format has just been changed

Downgoat

if I had a challenge that said "take input n and add one", it would be a dupe of "take input n and add two"

if the answers will be extermly similar than two posts are closed as dupe

ColdGolf

@Downgoat The input of the dupe is the output in my challenge. It's reversed.

Downgoat

Though please checkout the Sandbox you can get feedback on challenge before its posted. People can find problems with it and dupes can be identified early

> if the answers will be extermly similar

hm

ColdGolf

How much similar is it?

It's not similar enough that you can reuse your code for both posts.

Rohan Jhunjhunwala

11:52 PM

@Downgoat its interesting that ColdGolf came in with a question about the very compression algorithm I was justing. The algorithm is provably ineffective for pi, but it works on text with a lot of repeated characters. Run length encoding would have a theoretical upper bound of log(n) and an upper bound of 2*n (citation needed)

Downgoat

ok I guess it's sufficiently different

voted to repoen

ColdGolf

@Downgoat Thanks! @RohanJhunjhunwala You too?

Downgoat

@ColdGolf though btw, use code-blocks for examples and headings to avoid downvotes

Rohan Jhunjhunwala

Personally I feel that it is a simple difference in the input requirement. Let me take a deeper look at it.

Voted to reopen, but it is likely to receive more downvotes as it is just a modification in the input format. Usually inputs here are very open (sometimes too open)

ColdGolf

@RohanJhunjhunwala Thanks!

Conor O'Brien

11:55 PM

@Downgoat you're looking for some kind of segmented encoding? It can't be very sufficieny

*efficient

Rohan Jhunjhunwala

@Downgoat @ConorO'Brien I feel like such an encoding is highly unlikely to work for a number like pi. In fact it is proven ineffective to try to compress pi. (it becomes a problem of lossless compression on random data)

Transcript for