# Generate an infinite group of infinite galaxies [closed]

Here is the challenge as proposed by @trichoplax thanks to him for consolidating my post and standarizing it to PPCG common-rules.

• A galaxy is a group of numbers where each one is mapped to another via a precise function f either a symbolic one or mathematical, a structure of numbers sharing some common points with this challenge i got inspired from with an exception that a galaxy sequence is not cyclic, but holds in a black hole, where more than one number can be mapped to it.
• A black hole is a specific unique number from a galaxy where all numbers (not individually) are mapped transitively to it, by repeating a function f infinitely over an infinite far number in a same galaxy, or just once if a number is the closest in the same galaxy, for example if the function is the ceiling of the square root then a black hole for the biggest galaxy so far excluding only the number 1 is 2, because mapping the closest number 3 or the infinite repetitively leads to the same number.

Conceive a universe of an infinite number of distinct galaxies where all galaxies encompass an infinite number of integers.

Note that the example of ceiling of square root is banned for two reasons:

• The galaxy {1} is finite.
• There is a finite number of galaxies.

A valid example, is dividing by the smallest prime factor. This gives an infinite number of infinite galaxies.

2*2*3*5*5*7, 2*3*5*5*7, 3*5*5*7, 5*5*7, 5*7, 7, 7*5*5*5, 7*5*5*5....
5*5*7*11, 5*7*11, 11*7*7*7... , ....
...

Or one galaxy as a tree:

2*2*5 - 2*5 \
\
2*3*5 - 3*5 - 5
3*3*5 /       |
/
2*5*5 - 5*5 /
3*5*5 /

Each galaxy consists of all numbers that share the same largest prime factor, and the function takes them all step by step towards the black hole which is that prime factor.

Note also, you may choose any domain of integers as long as the range is infinite, i mean you can exclude a range of numbers that makes the rest still boundless like {1,0} from last example.

Your program takes any integer input via a function's dimension , STDIN, and outputs an integer as the image mapped from this preimage, otherwise prints "error" or any string prespecified for an outputless range of enteries.

For the same example:

(IN/OUTPUT)

20
10

15
5

77
11

0
'undefined'

1
'undefined'

This is so shortest program in bytes wins.

I would have really liked to add a bonus-score for anyone who succeeds to find a function generating a universe without trees, alas, bonuses for code-golf are excluded.

## closed as unclear what you're asking by xnor, Mego♦, Blue, Rɪᴋᴇʀ, Erik the OutgolferJun 2 '16 at 13:08

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Do they have to have common points? – Leaky Nun May 27 '16 at 11:08
• To clarify: a "black hole" is a fixed point of the function f (a number n such that f(n) = n), and a "galaxy" is the set of all numbers that eventually reach the same black hole when f is applied to them repeatedly, correct? And the challenge is to implement a function f that has an infinite number of infinitely large galaxies? Can f have finite cycles or finite galaxies in addition to these infinite galaxies? – Zgarb May 27 '16 at 12:27
• Also, you might want to add that in your example, every prime is a black hole (so the function is actually "divide by smallest prime factor, unless input is prime; in that case do nothing"). This has caused some confusion. – Zgarb May 27 '16 at 12:47
• That six-line sentence in the second item is... not the easiest I've read :-) – Luis Mendo May 27 '16 at 16:04
• I still don't understand what this is asking, and based on discussion in answer comments, I'm not the only one. Can someone please state the requirement in standard mathematical terminology? – xnor Jun 1 '16 at 19:46

# Pyth, 5 4 bytes, no trees

I am working under the assumption that the author intended for the function to be surjective, and for “no trees” to mean that only black holes have multiple preimages. (Technically, a tree with only one branch is still a tree.)

ahxt

Domain: positive integers. Function: f(x) = |((x − 1) XOR x) + 1 − x|. Black holes: powers of 2. Galaxies:

1 ← 3 ← 5 ← 7 ← 9 ← 11 ← ⋯,
2 ← 6 ← 10 ← 14 ← 18 ← 22 ← ⋯,
4 ← 12 ← 20 ← 28 ← 36 ← 44 ← ⋯,
8 ← 24 ← 40 ← 56 ← 72 ← 88 ← ⋯,

• please you can knock away that assumption u deduced by urself that a domain is surjective, the only condition for my puzzle, that numbers are either bridged to a "spleen" or "blackhole" or "terminus" by other peers, or just it is drawn directly to this point, maybe i made a slip here, so i should rather use "and" ? – Abr001am May 29 '16 at 10:57
• @Agawa001 This solution is valid whether or not the function is required to be surjective. However, if it is not, then my non-surjective 2-byte solution is also valid and also has no trees, which would make this 5-byte solution kind of pointless. (It is apparent that you have some complaint about my 2-byte solution, but I still cannot figure out what that complaint is. Let’s keep that conversation over there.) – Anders Kaseorg May 29 '16 at 11:25
• i cant understand your solution, it does subtract the rearmost runs of 0's followed by '1' shifted by 1 from x, does it have another translation ? – Abr001am May 29 '16 at 11:45
• is this a universe with tree-less infinite galaxies ? even for bh's ? if so i would accept that unique answer. – Abr001am May 29 '16 at 11:46
• @Agawa001 You are going to have to explain what you mean by “tree-less”. What is a “tree”? Formally, a tree is any graph where there is a unique path from the root to each node. That is not the case in any graph with a self-loop (such as a black hole). If you exclude the self-loops, then every galaxy in every valid solution is a tree. I am doing my best to try to infer what you meant to say, but that is clearly not working, and this would be much clearer to me and to everyone else if you could give a formal definition. – Anders Kaseorg May 29 '16 at 11:56

# Python 2, 15 bytes

lambda n:n>>n%2

The domain is nonnegative integers.

• You ninja'd me :( I was just discussing this in chat... – orlp May 27 '16 at 13:11
• @orlp If I'm understanding the question correctly, 0, 1, 3, 7, ... is a galaxy. – feersum May 27 '16 at 13:15
• Does 2 form an infinite galaxy? – Leaky Nun May 27 '16 at 13:19
• @LeakyNun Yep. 2, 5, 11, 23, etc. – feersum May 27 '16 at 13:20
• @feersum I confused it with a different solution, never mind :) – orlp May 27 '16 at 13:21

# Python, 40 bytes

lambda n:n&~-n and int(bin(n)[3:],2)or n

Clear the top bit if there's more than one bit set, otherwise returns the number itself. The domain is the positive integers.

First couple numbers (in binary):

1:     1
10:    10
11:     1
100:   100
101:     1
110:    10
111:    11
1000:  1000
1001:     1
1010:    10
1011:    11
1100:   100
1101:   101
1110:   110
1111:   111
10000: 10000
10001:     1
10010:    10
10011:    11
10100:   100
10101:   101
10110:   110
10111:   111
11000:  1000
11001:  1001
11010:  1010
11011:  1011
11100:  1100
11101:  1101
11110:  1110
11111:  1111
• this is nice one ! – Abr001am May 27 '16 at 13:06

# Pyth, 2 bytes

hP

Domain: integers ≥ 2. Function: smallest prime factor. Black holes: primes.

(This seems too simple but seems to satisfy the challenge as far as I can tell. Is the challenge missing some requirement? For example, perhaps the function is supposed to be surjective?)

• " all members must be mapped to a blackhole transitively or directly" hmmm that does not satisfy the "transitively" condition. but I will take it as valid solution. – Abr001am May 28 '16 at 23:11
• @Agawa001 The condition that you wrote is satisfied—“all numbers are A or B” does not require “some numbers are A”. But I think this solution is not interesting, so if you fix the challenge requirements to exclude it, I am happy to delete it. I would suggest that you add a requirement that the function is surjective. (That would imply the existence of arbitrarily long transitive chains to any black hole.) – Anders Kaseorg May 28 '16 at 23:16
• the function is already surjective, but it can be bijective where there is no trees, i dont know how u relate things – Abr001am May 28 '16 at 23:20
• @Agawa001 No it isn’t. Surjectivity is when the image is the entire codomain: that is, for every y, there is at least one x with f(x) = y. en.wikipedia.org/wiki/Surjective_function – Anders Kaseorg May 29 '16 at 0:11
• @Agawa001 Your requirement is an “or”, so I get to choose which side of the “or” to satisfy. If I choose “directly” every time, I have satisfied the requirement. If that is not what you intended, you should change the requirement. (Besides, “directly” is a special case of “transitively” anyway. Also, my name is not andres.) – Anders Kaseorg May 29 '16 at 8:25

# Python 2, 29 bytes

lambda n:int("0"+n[1:])or n

Strips off the first digit, unless that makes the number 0. The domain is the positive integers.

## 05AB1E, 9 bytes

Code:

Dpiëf¬¹s/

Explanation:

Dpi         # if input is prime return input
ë        # else
f¬      # get the smallest primefactor
¹s/   # divide input by this factor

Domain:{n | n∈N ∧ n>1}

Range: {n | n∈N ∧ n>0}

• please, provide the range of surjective (domain,codomain) and the function used (even if it is already embedded in the question core) – Abr001am May 27 '16 at 10:57
• @Agawa001: Something like this? – Emigna May 27 '16 at 11:11
• I guess you might have to update your code. – Leaky Nun May 27 '16 at 12:44
• @LeakyNun: Thanks for the heads up – Emigna May 27 '16 at 13:11

## JavaScript (ES6), 12 bytes

n=>n%2?n:n/2

The domain is the positive integers. The black holes are the odd numbers.

• n=>n/(2-n%2) has the same byte count – Leaky Nun May 27 '16 at 13:21

# Pyth, 5 bytes

|stzz

Port of my Python answer (the decimal version).

## matlab (156)

a=input('');if find(num2str(a)=='0')a,return,end,b=char(num2str(a)-1);c=str2num(b);if find(b=='0')if(find(num2str(c)=='0')&c)c,else 10^nnz(b)+c,end,else c,end
• I declare my self the winner of that imaginary score because i am the first who finds a universe of galaxies without trees.

• Domain is decimal numbers with two or more significant digits. and not a difference bteween two arbitray digits squals to 9 .

• Black holes are numbers which have significant zeros, either in the extreme bottom, or between two strictly positive digits 12300131 , 123400 , 10 , ....

• The function is decrementing all decimal digits of that number by 1, if we stumble upon a significant zero we declare a blackhole, if non-significant zero at the head of this number, precede it with 1 then the result topped by unsignificant zeos.

• There is no trees in that galaxy except the blackhole which absorbs an infinite tree-less streams of finite numbers.

• I don’t understand how this fits your requirements. 11 maps to 0, which is not in your domain. And the galaxies are not infinite; for example, the galaxy 98 → 87 → 76 → 65 → 54 → 43 → 32 → 21 → 10 has no other members. – Anders Kaseorg May 28 '16 at 23:35
• @downvoter fixed – Abr001am May 29 '16 at 8:01
• @AndersKaseorg they do have infinite other members , 232 → 121 → 10 , 2232 → 1121 → 10 , 22222232 → 11111121 → 10 ..... – Abr001am May 29 '16 at 8:04
• @AndersKaseorg and for ur remark it is fixed, i replaced 9 by 1, now : 22 → 11 → 100 / 322 → 211 → 100 / ..... – Abr001am May 29 '16 at 8:07
• Your change added other preimages of 10, but now the galaxy 90 has no other members. – Anders Kaseorg May 29 '16 at 8:49